一道比较规整的最优化题。
首先,因为 OFF/ON 又会覆盖掉之前的影响,也就是说,在 OFF/ON 之前做的
TOG 操作可能被覆盖掉而白费力气,所以,所有的 TOG 操作都在 OFF/ON
之后一定不劣。
那我们先考虑,如果只做 OFF/ON 操作,怎么找到最优次数。
我们可以先不管序列
怎么样,只根据序列
的形态找到一个答案上界。事实上,序列
中一段连续的相等数可以缩为一个。如果缩完之后形如 ,那就需要 的个数那么多次操作,如果形如 ,那就需要 的个数再加 。总而言之,就是 。
那么序列 有什么用呢?对于
的位置,我们可以将其左边和右边分成两部分来处理,也可以不分。按照这些位置分完部分(注意这个部分与上文的"连续段"是不同的概念)后,直接套用上述结论即可得到最优次数。
那么 TOG 操作怎么处理?其实是简单的,因为 TOG 操作肯定最后进行,且
TOG 操作是可逆的,所以完全可以看作:对序列 进行 TOG 操作。
因为决策还是有点复杂,考虑设计 DP 状态 ,表示 DP 到前 位,第二维表示当前处于一个以 开头的部分中,或用 表示不处于任何一个部分中, 表示当前位有没有被 TOG
操作覆盖。转移是简单的,分类讨论即可,时间复杂度 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; template<typename T> inline bool ckmin(T &x,const T &y) { return (y < x) && (x = y,true);} int n,a[N],b[N]; string str; int dp[N][3][2]; int main() { cin >> n; cin >> str; for(int i = 1;i <= n;i++) a[i] = str[i - 1] - '0'; cin >> str; for(int i = 1;i <= n;i++) b[i] = str[i - 1] - '0'; memset(dp,0x3f,sizeof dp); dp[0][2][0] = 0; for(int i = 1;i <= n;i++) for(int rv = 0;rv < 2;++rv) for(int lv = 0;lv < 2;++lv) { int tb = b[i] ^ rv,lb = b[i - 1] ^ lv; ckmin(dp[i][0][rv],dp[i - 1][0][lv] + (lb == 1 && tb == 0) + (lv == 0 && rv == 1)); if(tb == 0) ckmin(dp[i][0][rv],dp[i - 1][2][lv] + 1 + (lv == 0 && rv == 1)); ckmin(dp[i][1][rv],dp[i - 1][1][lv] + (lb == 0 && tb == 1) + (lv == 0 && rv == 1)); if(tb == 1) ckmin(dp[i][1][rv],dp[i - 1][2][lv] + 1 + (lv == 0 && rv == 1)); if(a[i] == tb) ckmin(dp[i][2][rv],min({dp[i - 1][0][lv] + (lb != 0),dp[i - 1][1][lv] + (lb == 0),dp[i - 1][2][lv]}) + (lv == 0 && rv == 1)); } int ans = 1e9; for(int a = 0;a < 3;a++) for(int t = 0;t < 2;t++) ckmin(ans,dp[n][a][t] + (a < 2 ? (b[n] ^ t) != a : 0)); cout << ans << endl; return 0; }
|