当前位置: 代码迷 >> 综合 >> 51nod 2484 小b和排序(DP)
  详细解决方案

51nod 2484 小b和排序(DP)

热度:22   发布时间:2024-01-15 06:39:09.0

小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;
}