正文
Codeforces Round #354 (Div. 2) C. Vasya and String
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目链接：
http://codeforces.com/contest/676/problem/C
题解：
把连续的一段压缩成一个数，对新的数组求前缀和，用两个指针从左到右线性扫一遍。
一段值改变一部分的情况考虑的不够周到，wa了两次。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std; const int maxn = + ;
char str[maxn];
int arr[maxn], tot;
int sum[maxn]; int n, k; int solve(int fst) {
int ret = -, cnt = ;
int p1 = fst;
for (int p2 = fst; p2 <= tot; p2 += ) {
cnt += arr[p2];
while (p1 <= p2&&cnt > k) {
cnt -= arr[p1]; p1 += ;
}
if (p1 <= p2) {
if (p1 - >= && p2 + <= n) {
ret = max(ret, sum[p2 + ] - sum[p1 - ]+k-cnt);
ret = min(ret, n);
}
else if (p1 - >= ) {
ret = max(ret, sum[p2] - sum[p1 - ] + k - cnt);
ret = min(ret, n);
}
else if (p2 + <= n) {
ret = max(ret, sum[p2 + ] - sum[p1 - ] + k - cnt);
ret = min(ret, n);
}
else {
ret = max(ret, sum[p2] - sum[p1 - ] + k - cnt);
ret = min(ret, n);
}
}
}
return ret;
} int main() {
while (scanf("%d%d", &n, &k) == && n) {
scanf("%s", str);
tot = ;
int cnt = ;
for (int i = ; i < n - ; i++) {
if (str[i] != str[i + ]) {
arr[++tot] = cnt;
cnt = ;
}
else {
cnt++;
}
}
arr[++tot] = cnt;
sum[] = ;
for (int i = ; i <= tot; i++) sum[i] = sum[i - ] + arr[i];
int ans = ;
for (int i = ; i <= tot; i++) {
ans = max(ans, arr[i] + k);
ans = min(ans, n);
}
ans = max(ans, solve());
ans = max(ans, solve());
printf("%d\n", ans);
}
return ;
} /*
4 2
abba
8 1
aabaabaa
5 2
ababa
5 1
ababa
4 1
aaba
5 0
aaaaa
*/
