51nod 2484 小b和排序（DP）

小b有两个长度都为n的序列A,B。

现在她需要选择一些i，然后交换A[i]和B[i]，使得A和B都变成严格递增的序列。

你能帮小b求出最少交换次数吗？

输入保证有解。

 收起

输入

第一行输入一个正整数n，表示两个数组的长度； 第二行输入n个数，表示A[i]，以空格隔开； 第三行输入n个数，表示B[i]，以空格隔开； 其中1≤n≤1000, 0≤A[i],B[i]≤2000

输出

输出一个数，表示交换次数

输入样例

4 1 3 5 4 1 2 3 7

输出样例

1

分析：

DP如此奇妙

dp[i][0]表示在i不反转

dp[i][1]表示在i反转

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int a[N],b[N],dp[N][3];
int main()
{
    int n,m;
    scanf("%d",&n);
    int sum1=0,sum2=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&b[i]);
    }

    a[0]=b[0]=-1;
    memset(dp,127,sizeof(dp));
    dp[0][0]=dp[0][1]=0;
    
    
    for(int i=1;i<=n;i++)
    {
        if(a[i]>a[i-1]&&b[i]>b[i-1]) 
        {
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
            dp[i][1]=min(dp[i][1],dp[i-1][1]+1);
        }
        if(a[i]>b[i-1]&&b[i]>a[i-1])
        {
            dp[i][0]=min(dp[i][0],dp[i-1][1]);
            dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
        }
        
    }
    cout<<min(dp[n][0],dp[n][1])<<endl;
  
    return 0;
}