【LOJ 3037】开关游戏(DP)
开关游戏
题目链接:LOJ 3037
题目大意
给你两个 01 串,分别是初始串和目标串,你可以有三种操作:选择一个区间,把区间里面的都变成 0/1,或者把区间里面的 01 反转。
问你最少要操作多少次把初始串变成目标串。
思路
考虑每个位置最后的结果会受什么印象。
首先是覆盖这个区间的操作,接着一个变成
0
/
1
0/1
0/1 的会取消前面所有的作用,那就是可能是前面有变成
0
/
1
0/1
0/1,再配一个可能的翻转(因为两次的话就相当于抵消了,而且没有必要)
那你可以考虑从左往右考虑,直接记录当前点的覆盖状态(根据是否有覆盖和根据是否有翻转,一共
6
6
6 种状态)。
然后考虑从这个点的
x
x
x 状态到下一个点的
y
y
y 状态,要花费多少次数。
那这个因为是区间,所以我们是能继承就继承,要停止就停止,要新增才需要增加操作次数。(类似区间拆成扫描线)
不过要注意的是要判断当前状态是否能使得这个点变成目标串里面的数字。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 1e6 + 100;
int n, a[N], b[N];
int f[N][3][2], ans;
//0:没有,1:强制变成0,2:强制变成1
//0:没有,1:翻转
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%1d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%1d", &b[i]);
memset(f, 0x7f, sizeof(f)); ans = f[0][0][0]; f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 2; j++)
for (int k = 0; k <= 1; k++) {
for (int jj = 0; jj <= 2; jj++)
for (int kk = 0; kk <= 1; kk++) {
if (jj == 0 && ((a[i] ^ b[i]) ^ kk)) continue;
if (jj != 0 && ((jj - 1) ^ kk) != b[i]) continue;
int now = f[i - 1][j][k];
if (jj && (jj != j)) now++;
if (kk && !k) now++;
f[i][jj][kk] = min(f[i][jj][kk], now);
}
}
}
for (int j = 0; j <= 2; j++)
for (int k = 0; k <= 1; k++)
ans = min(ans, f[n][j][k]);
printf("%d", ans);
return 0;
}
相关文章
- 【洛谷1640】[SCOI2010]连续攻击游戏
- 【BZOJ3875】[Ahoi2014&Jsoi2014]骑士游戏 SPFA优化DP
- 【BZOJ4820】[Sdoi2017]硬币游戏 AC自动机+概率DP+高斯消元
- 【BZOJ1915】[Usaco2010 Open]奶牛的跳格子游戏 DP+单调队列
- 《HTML5 2D游戏编程核心技术》——第3章,第3.2节实现平滑的HTML5动画
- 动态规划(DP)之多边形游戏问题
- Android游戏开发详解》一第1章 程序设计基础
- 《Android游戏开发详解》一3.3 接口
- 《点睛:ActionScript3.0游戏互动编程》——1.2 ColorTransform对RGB数值的操作及应用
- 《Cocos2D-X游戏开发技术精解》一1.10 本章小结
- Swift - 多层无缝循环滚动背景(SpriteKit游戏开发)
- 游戏开发经验之没有美工程序员是如何制作游戏的
- 【bzoj3875】[Ahoi2014&Jsoi2014]骑士游戏 Spfa优化dp
- 1233: 传球游戏 [DP]