51nod-2484-小b和排序

题目：

小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]代表交换使得满足要求的最少交换次数。进行状态转移时，进行a,b数组的比较，选最小值(具体看代码)

代码:

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
int dp[1010][2];
int a[1010],b[1010];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    dp[0][1] = 1;
    for(int i = 1; i < n; i++){
        dp[i][0] = dp[i][1] = 99999;
    }
    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);
        }
    }
    printf("%d\n", min(dp[n - 1][0], dp[n - 1][1]));
    return 0;
}