题目描述
https://codeforces.com/problemset/problem/900/E
Solution
注意到在预处理之后我们可以 $O(1)$ 判断一段区间是否可以组成对应的子串
所以我们令 $f[i]$ 表示到 $i$ 为止,最多有多少个给定串,$g[i]$ 表示在 $f[i]$ 最大的情况下所需要的最少操作
时间复杂度 $O(n)$
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
| #include <iostream> #include <cstdio> #define maxn 100010 using namespace std;
int n, m;
char s[maxn];
int a[maxn], b[maxn], p[maxn];
int f[maxn], g[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> s + 1 >> m; int la = m + 1 >> 1, lb = m / 2; for (int i = 1; i <= n; ++i) if (s[i] == 'a') a[i] = a[i - 2] + 1, b[i] = 0, p[i] = p[i - 1]; else if (s[i] == 'b') b[i] = b[i - 2] + 1, a[i] = 0, p[i] = p[i - 1]; else a[i] = a[i - 2] + 1, b[i] = b[i - 2] + 1, p[i] = p[i - 1] + 1; for (int i = 1; i <= n; ++i) { f[i] = f[i - 1]; g[i] = g[i - 1]; if (m & 1 && a[i] >= la && b[i - 1] >= lb || m % 2 == 0 && b[i] >= lb && a[i - 1] >= la) if (f[i - m] + 1 > f[i]) f[i] = f[i - m] + 1, g[i] = g[i - m] + p[i] - p[i - m]; else if (f[i - m] + 1 == f[i]) g[i] = min(g[i], g[i - m] + p[i] - p[i - m]); } cout << g[n] << "\n"; return 0; }
|