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();
}