观察式子 \(a\times L_0+L_1\)，一个显然的想法是“定一求一”，即预处理求出对于每个 \(L_1\) 最大的 \(L_0\)，然后对于每个 \(a\)，枚举 \(L_1\)，统计最大的 \(a\times L_0+L_1\)。这样，我们将问题转化为了：已知 \(L_1=len\)，求出 \(dp_{len}=L_{0max}\)。
dp 数组的状态是“长度”，这似乎并不好维护，我们不得不把它落实到一个个子段上去：对于每个 \(len\in [1,n]\)，枚举长度为 \(len\) 的子段，并用 \(x\) 次操作把它改为一个全 \(1\) 段，这就是 \(L_1\) 对应的子段。然后，在它的左边和右边，去寻找 \(L_0\)（利用好剩下的 \(k-x\) 次操作使其尽可能大）并更新 \(dp_{len}\)。
问题是，仅仅枚举子段的复杂度就到了 \(O(n^2)\)，意味着我们需要预处理出前后缀 \(1\sim i\) 中修改至少 \(j\) 次能得到的最大 \(L_0\)，分别设为 \(pre_{i,j},suf_{i,j}\)。通用的方法是“两步走”：以前缀为例，先求出以 \(i\) 结尾的，修改了恰好 \(j\) 次的最大 \(L_0\)；再应用类似前缀 \(\max\) 的方法得到答案。
启示：
- 动态规划设计状态应该尽可能简洁，既能清晰的表示当前情形，又不包含冗余信息；
- 研究复杂的问题可以层层深入，把大问题分解为一个个小问题，各个击破。
下面是 AC 代码：
void solve() {
int n, k;
string s;
cin >> n >> k >> s;
// 以 i 结尾，修改 j 次的最大 0 段长度
vector<vector<int>> pre(n, vector<int>(k + 1, 0));
pre[0][0] = (s[0] == '0');
if (k > 0) {
pre[0][1] = (s[0] == '1');
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= min(i + 1, k); j++) {
if (s[i] == '0') {
pre[i][j] = pre[i - 1][j] + 1; // s[i] = 0, 不修改
} else if (j > 0) {
pre[i][j] = pre[i - 1][j - 1] + 1; // s[i] = 1, 修改
} else {
pre[i][j] = 0; // s[i] = 1, 不修改
}
}
}
// 将 pre 改为在 i 及 i 之前结尾，最多修改 j 次的最大 0 段长度
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
pre[i][j] = max(pre[i][j], pre[i - 1][j]);
if (j > 0) {
pre[i][j] = max(pre[i][j], pre[i][j - 1]);
}
}
}
// 以 i 开头，修改 j 次的最大 0 段长度
vector<vector<int>> suf(n, vector<int>(k + 1, 0));
suf[n - 1][0] = (s[n - 1] == '0');
if (k > 0) {
suf[n - 1][1] = (s[n - 1] == '1');
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= min(n - i, k); j++) {
if (s[i] == '0') {
suf[i][j] = suf[i + 1][j] + 1; // s[i] = 0, 不修改
} else if (j > 0) {
suf[i][j] = suf[i + 1][j - 1] + 1; // s[i] = 1, 修改
} else {
suf[i][j] = 0; // s[i] = 1, 不修改
}
}
}
// 将 suf 改为在 i 及 i 之后开头，最多修改 j 次的最大 0 段长度
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
suf[i][j] = max(suf[i][j], suf[i + 1][j]);
if (j > 0) {
suf[i][j] = max(suf[i][j], suf[i][j - 1]);
}
}
}
vector<int> sum(n, 0);
sum[0] = s[0] - '0';
for (int i = 1; i < n; i++) {
sum[i] = sum[i - 1] + s[i] - '0';
}
// dp[len] 为 L1 = len 时的最大 L0
vector<int> dp(n + 1, -1);
dp[0] = max(pre[n - 1][k], suf[0][k]);
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int len = r - l + 1;
// [l, r] 中 0 的个数
int x = len - (sum[r] - (l > 0 ? sum[l - 1] : 0));
if (x > k) {
continue;
}
if (l == 0 && r == n - 1) {
dp[len] = max(dp[len], 0);
continue;
}
if (l > 0) {
dp[len] = max(dp[len], pre[l - 1][k - x]);
}
if (r < n - 1) {
dp[len] = max(dp[len], suf[r + 1][k - x]);
}
}
}
for (int a = 1; a <= n; a++) {
int ans = 0;
for (int len = 0; len <= n; len++) {
if (dp[len] == -1) {
continue;
}
ans = max(ans, a * dp[len] + len);
}
cout << ans << " ";
}
cout << endl;
}