CF603
CF603A
CF603A题意
现有一个长度为 \(n\) 的 01 串, 可以进行一次区间翻转 ( 起点终点随意, 并且区间里的值 1 变 0, 0 变 1 ), 得到一个新的 01 串, 使得得到的新的 01 串中的一个子串最长 (子串不一定连续), 且这个子串是 01 间隔的，没有连续两个字符相同。比如 0101 , 101 和1010 是合法的, 100, 1100 是不合法的。试求翻转后最长 01 间隔子串的长度。
CF603A题解
设 \(f_{i,0/1/2}\) 分别表示 \(i\) 没有反转，\(i\) 前面没有反转区间 / \(i\) 没有反转，\(i\) 前面有反转区间 / \(i\) 反转，\(i\) 前面有反转区间 的情况下最长 \(01\) 子串。
那么显然有
\[f_{i,0}=f_{i-1,0}+[a_i\not= a_{i-1}]\\
f_{i,1}=\max{f_{i-1,[a_i=a_{i-1}] + 1}+1,f_{i-1,[a_i\neq a_{i-1}]+1}}\\
f_{i,2}=\max{f_{i-1,2}+[a_i\neq a_{i-1}],f_{i-1,0}+[a_i=a_{i-1}]}
\]
没了。
CF603A代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f= 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
int n;
char ch[maxn];
int f[maxn][3];
signed main(){
n = read();scanf("%s",ch + 1);
int ans = 1;
f[1][0] = f[1][1] = f[1][2] = 1;
for(int i = 2;i <= n;i++){
f[i][0] = f[i - 1][0] + (ch[i] != ch[i - 1]);
f[i][1] = max(f[i - 1][1 + (ch[i] == ch[i - 1])] + 1,f[i - 1][1 + (ch[i] != ch[i - 1])]);
f[i][2] = max(f[i - 1][2] + (ch[i] != ch[i - 1]),f[i - 1][0] + (ch[i] == ch[i - 1]));
ans = max(max(ans,f[i][0]),max(f[i][1],f[i][2]));
}
printf("%d\n",ans);
return 0;
}