题意： 一行有 n 个数字，是 1 ~ n 的一个排列， 现在， 给你 n 个数， 0 代表这个数还没有填好。 然后，现在定义这 n 个数的复杂度是 相邻两个数的奇偶性不同的组数。
例如， 5 1 2 3 4 这一个排列的复杂度是 （1，2），（2，3），（3，4） = 3； 现在问你把那些 0 填上数字，最低的复杂度是多少。
解： 有两种做法。
一、贪心（比较复杂）
对每段连续的0，维护一个 l, r, num； 代表 这段连续的 0 左边第一个非0的数的奇偶性，若，左边没有非0数，则 l = -1； r 同理。
num则代表0的个数。 然后， 对于所有的连续的0，按照num从小到大排序，优先，填那些 num 较小的且 左右端点奇偶性相等的段。
因为，奇偶性相等的，若你不填它，它会产生2的贡献。 而，左右端点奇偶性不同的，无论你怎么填，它都是1的贡献。
但是，对于 l = -1 和 r = -1 这种情况的，你填满它可以减少1的贡献，你不填则产生1的贡献。 所以， 优先填奇偶性相等的，因为填满可以减少2的贡献。
然后，再考虑 l = -1 和 r = -1 的情况。 即可。
#include <bits/stdc++.h> #define LL long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF INT_MAX #define inf LLONG_MAX using namespace std; const int N = 1e6 + 5; int a[N]; struct note { int l, r, num; bool flag; note(int l, int r, int num) : l(l), r(r), num(num) { flag = false; } bool operator < (const note& a) const { return num < a.num; } }; vector<note> Q; int main() { int n; scanf("%d", &n); int ans = 0; int ji = n / 2, ou = n / 2; if(n & 1) ji++; a[0] = -1; a[n + 1] = -1; rep(i, 1, n) { scanf("%d", &a[i]); if(a[i - 1] > 0 && a[i] > 0) ans += (a[i - 1] & 1) ^ (a[i] & 1); if(a[i]) { if(a[i] & 1) ji--; else ou--; } } if(n == 1) return puts("0"),0; if(ji == (n + 1) / 2 && ou == n / 2) return puts("1"),0; rep(i, 1, n) { if(a[i] == 0) { int st = i; while(i <= n && !a[i]) i++; int l, r; if(a[st - 1] == -1) l = -1; else l = a[st - 1] & 1; if(a[i] == -1) r = -1; else r = a[i] & 1; Q.pb(note(l, r, i - st)); } } sort(Q.begin(), Q.end()); for(int i = 0; i < Q.size(); i++) { if(Q[i].l == Q[i].r) { if(Q[i].l) { if(ji >= Q[i].num) { Q[i].flag = true; ji -= Q[i].num; } } else { if(ou >= Q[i].num) { Q[i].flag = true; ou -= Q[i].num; } } } } for(int i = 0; i < Q.size(); i++) { if(Q[i].l == -1 || Q[i].r == -1) { int ch; if(Q[i].l != -1) ch = Q[i].l; else ch = Q[i].r; if(ch) { if(ji >= Q[i].num) { ji -= Q[i].num; Q[i].flag = true; } } else { if(ou >= Q[i].num) { ou -= Q[i].num; Q[i].flag = true; } } } } for(int i = 0; i < Q.size(); i++) { if(!Q[i].flag) { if(Q[i].l == Q[i].r) ans += 2; else ans++; } } printf("%d ", ans); return 0; }
二、DP
4维dp， dp[ i ][ j ][ k ][ op ] ： 1 ~ i 的 0 填了 j 个奇数， k 个偶数， 第 i 个数是 op 的最低复杂度。 op = 1 代表奇数， op = 0代表 偶数。
然后 j + k 必须 小于等于 1 ~ i 中 0 的个数 now0 才能转移。 然后分成 a[ i ] != 0 和 a[ i ] = 0 两种情况。
a[ i ] 不等于0，则根据 a[ i ] 的奇偶性直接从前面转移过来就行了。
a[ i ] 等于0， 则又分为a[ i ] 是奇数， a[ i ] 是偶数两种情况。
#include <bits/stdc++.h> #define LL long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF 0x3f3f3f #define inf LLONG_MAX using namespace std; const int N = 1e6 + 5; int a[N]; int dp[101][101][101][2]; int main() { int n; scanf("%d", &n); int ans = 0; int ji = n / 2, ou = n / 2; if(n & 1) ji++; rep(i, 1, n) { scanf("%d", &a[i]); if(a[i]) { if(a[i] & 1) ji--; else ou--; } } if(n == 1) return puts("0"),0; if(ji == (n + 1) / 2 && ou == n / 2) return puts("1"),0; mem(dp, INF); dp[0][0][0][0] = dp[0][0][0][1] = 0; int now0 = 0; rep(i, 1, n) { if(!a[i]) now0++; rep(j, 0, ou) { rep(k, 0, ji) { if(j + k <= now0) { if(a[i] > 0) { if(a[i] & 1) dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]); else dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1); } else { dp[i][j][k][0] = min(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k][1] + 1); dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0] + 1, dp[i - 1][j][k - 1][1]); } } } } } printf("%d ", min(dp[n][ou][ji][0], dp[n][ou][ji][1])); return 0; }