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

思路：贪心：如果ai, bi 不大于前面两个(i - 1) 中的较大数，那么交换后就会对序列单调性产生影响，这时候我们称之为有限制的对数，如果都大于的话那么就不会产生这种影响，用cnt记录需要交换的次数，用sum记录有限制的对数。可以将其看成许多区间，每个区间的终点就是没有限制的一对数，遇到终点就更新答案，要不就是交换需要交换的，要不就交换交叉限制的，后面正限制的也会受影响。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3 + 10; int a[maxn], b[maxn]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 1; i <= n; ++i) scanf("%d", &b[i]); int ans = 0, cnt = 0, sum = 0; // 答案， 必须交换的对数，有限制的对数 for(int i = 2; i <= n; ++i) { int tmp = max(a[i - 1], b[i - 1]); if(a[i] > tmp && b[i] > tmp) //如果都大于，就更新这一区间，下个结点当作新的区间 { ans += min(cnt, sum - cnt + 1); //后面那个是相当于这个小区间长度减去交叉限制的对数，长度是sum+1 sum = cnt = 0; } else { if(a[i] <= a[i - 1] || b[i] <= b[i - 1]) //必须要交换 { ++cnt; //正限制 swap(a[i], b[i]); } ++sum; } } if(cnt) //如果最后一次循环结束没有计数 ans += min(cnt, sum - cnt + 1); printf("%d\n", ans); return 0; } /* 33 1 2 4 6 7 10 13 14 18 16 22 20 22 23 28 30 29 30 31 33 40 41 42 44 47 47 54 58 57 61 62 64 65 1 3 5 8 9 8 12 16 15 20 18 24 25 26 24 25 33 34 37 38 38 39 42 45 46 49 52 56 59 60 62 63 65 */

DP

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3 + 10; int a[maxn], b[maxn]; int dp[maxn][2]; // 1表示交换，0表示不交换 int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 1; i <= n; ++i) scanf("%d", &b[i]); memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0, dp[1][1] = 1; //初始化 for(int i = 2; 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]) //对角线大于，要不就在i-1交换，要不就在i交换 { 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][0], dp[n][1])); return 0; } /* 33 1 2 4 6 7 10 13 14 18 16 22 20 22 23 28 30 29 30 31 33 40 41 42 44 47 47 54 58 57 61 62 64 65 1 3 5 8 9 8 12 16 15 20 18 24 25 26 24 25 33 34 37 38 38 39 42 45 46 49 52 56 59 60 62 63 65 */