美丽度的式子可以写成 \((a - 1) \times l_0 + (l_0 + l_1)\)，注意到 \(a \ge 1\)，也就是我们若固定了 \(l_0 + l_1\)，\(l_0\) 越大就越优。
于是我们可以预处理出对于所有的 \(p = l_0 + l_1\)，\(l_0\) 的最大值，设其为 \(g_p\)。回答时枚举 \(p = l_0 + l_1\)，贡献即为 \((a - 1) g_p + p\)。
考虑如何预处理。我们分类讨论 \(0\) 的最大区间在 \(1\) 的最大区间的左或者右。以在左边为例（右边类似），我们考虑枚举 \(1\) 最大区间的左右端点 \([l, r]\)，前缀和计算出要改 \(t\) 次，然后随着 \(l\) 往右移动，我们可以处理出所有右端点在 \(l\) 左侧的 \(0\) 最大区间，并得到 \(f_i\) 为用不超过 \(i\) 次修改 \(0\) 最大区间长度。然后 \(1\) 最大区间对 \(g\) 的贡献即为 \(g_{r - l + 1 + f_{k - t}} \gets \max(g_{r - l + 1 + f_{k - t}}, f_{k - t})\)。
注意一下 \(l_1 = 0\) 的 corner case。
时间复杂度 \(O(n^2)\)。赛时被这题卡了近 1h，没话说了。
code
// Problem: D. Trees and Segments
// Contest: Codeforces - Codeforces Round 893 (Div. 2)
// URL: https://codeforces.com/contest/1858/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 3030;
int n, m, a[maxn][2], f[maxn], g[maxn], h[maxn];
char s[maxn];
void solve() {
scanf("%d%d%s", &n, &m, s + 1);
for (int i = 0; i <= n + 1; ++i) {
f[i] = 0;
h[i] = -1e4;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= 1; ++j) {
a[i][j] = a[i - 1][j] + (s[i] == '0' + j);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
int len = j - i + 1, k = a[j][0] - a[i - 1][0];
if (k <= m) {
h[len + f[m - k]] = max(h[len + f[m - k]], f[m - k]);
}
}
for (int j = 1; j <= i; ++j) {
int len = i - j + 1, k = a[i][1] - a[j - 1][1];
f[k] = max(f[k], len);
}
for (int j = 1; j <= n; ++j) {
f[j] = max(f[j], f[j - 1]);
}
}
for (int i = 0; i <= m; ++i) {
h[f[i]] = max(h[f[i]], f[i]);
}
for (int i = 0; i <= n + 1; ++i) {
f[i] = 0;
}
for (int i = n; i; --i) {
for (int j = i; j; --j) {
int len = i - j + 1, k = a[i][0] - a[j - 1][0];
if (k <= m) {
h[len + f[m - k]] = max(h[len + f[m - k]], f[m - k]);
}
}
for (int j = i; j <= n; ++j) {
int len = j - i + 1, k = a[j][1] - a[i - 1][1];
f[k] = max(f[k], len);
}
for (int j = 1; j <= n; ++j) {
f[j] = max(f[j], f[j - 1]);
}
}
for (int i = 0; i <= m; ++i) {
h[f[i]] = max(h[f[i]], f[i]);
}
for (int i = 1; i <= n; ++i) {
int mx = 0;
for (int j = 1; j <= n; ++j) {
if (h[j] >= 0) {
mx = max(mx, h[j] * i + j - h[j]);
}
}
printf("%d ", mx);
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}