CF1858D Trees and Segments
给定一个长为 $n$ 的 $01$ 串 $s$ 和一个整数 $k$,你可以进行不超过 $k$ 次操作,每次操作是将某个位置反转($0$ 变 $1$,$1$ 变 $0$)。定义 $l_0$ 表示最长的连续 $0$ 的数量,$l_1$ 表示最长的连续 $1$ 的数量。
对于所有的 $a\in\{1,2,\cdots, n\}$,最大化 $al_0+l_1$,输出这个最大值。
多组数据,$\sum n\le 3000,\sum k\le 3000$。
核心思路:枚举 $l_1$,求最大的 $l_0$。
具体地,枚举全 $1$ 串所在的区间 $[l,r]$,那么将 $[l,r]$ 全变为 $1$ 的代价就是 $[l,r]$ 中 $0$ 的个数,设为 $x$。接着只需使用剩下的 $k-x$ 次在 $[1,l-1]$ 或 $[r+1,n]$ 中最大化 $l_0$(这里是“或”是因为左右两侧只有一侧能作为 $l_0$ 出现)。
故而我们需要处理出 $pre_{i,j}$ 表示前 $i$ 位,使用不超过 $j$ 次操作得到的最长全 $0$ 串的长度。方法:先求出 $pre_{i,j}$ 表示以 $i$ 为结尾,恰好使用 $j$ 次操作得到的最长全 $0$ 串的长度,有转移:
$$
pre_{i,j}=\begin{cases}
pre_{i-1,j} + 1 & s_i = 0\\
pre_{i-1,j-1}+1 & s_i = 1 \land j>0\\
0 & s_i=1 \land j = 0
\end{cases}
$$
然后做一次二维前缀 $\max$ 即可。
#include<bits/stdc++.h> namespace Acc { const int N = 3009; int pre[N][N], suf[N][N], f[N], a[N]; auto work = []() { int n, k; std::string s; std::cin >> n >> k >> s; s = ' ' + s; memset(f, -1, n + 1 << 2); for (int i = 1; i <= n; ++i) { if (s[i] == '0') { for (int j = 0; j <= k; ++j) { pre[i][j] = pre[i - 1][j] + 1; } } else { pre[i][0] = 0; for (int j = 1; j <= k; ++j) { pre[i][j] = pre[i - 1][j - 1] + 1; } } } for (int i = 1; i <= n; ++i) { for (int j = 0; j <= k; ++j) { pre[i][j] = std::max(pre[i][j], pre[i - 1][j]); } for (int j = 1; j <= k; ++j) { pre[i][j] = std::max(pre[i][j], pre[i][j - 1]); } } memset(suf[n + 1], 0, k + 1 << 2); for (int i = n; i; --i) { if (s[i] == '0') { for (int j = 0; j <= k; ++j) { suf[i][j] = suf[i + 1][j] + 1; } } else { suf[i][0] = 0; for (int j = 1; j <= k; ++j) { suf[i][j] = suf[i + 1][j - 1] + 1; } } } for (int i = n; i; --i) { for (int j = 0; j <= k; ++j) { suf[i][j] = std::max(suf[i][j], suf[i + 1][j]); } for (int j = 1; j <= k; ++j) { suf[i][j] = std::max(suf[i][j], suf[i][j - 1]); } } for (int i = 1; i <= n; ++i) { a[i] = a[i - 1] + (s[i] == '0'); } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { if (int x = a[j] - a[i - 1]; x <= k) { f[j - i + 1] = std::max({f[j - i + 1], pre[i - 1][k - x], suf[j + 1][k - x]}); } } } f[0] = pre[n][k]; for (int a = 1; a <= n; ++a) { int z = 0; for (int l = 0; l <= n; ++l) if (~f[l]) { z = std::max(z, a * f[l] + l); } std::cout << z << ' '; } std::cout << '\n'; }; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int T; std::cin >> T; while (T--) Acc::work(); }