题目大意：给出一个长度为n的仅由0和1的字符串，最多可以进行k次操作，每次操作可以将一个位置上的数取反。令a等于最大连续0的数量，令b等于最大连续1的数量，求i分别属于1~n时，i*a+b的最大值。
1<=n<=3000；0<=k<=n
思路：因为每个a，对应的b都不同，所以对于一个确定的i，我们只要求出当a为1~n中某个合法的数时，对应的最大的b是多少，然后枚举a求最大值即可。
我们令dp[i][j]表示修改j次，在[i,n]中最大有多少个1，首先大区间能从小区间转移，dp[i][j]=dp[i+1][j]，然后求出在i~n内0的数量cnt，dp[i][cnt]=max(dp[i][cnt],j-i+1)，然后修改j-1次能做到的，j此也能做到，dp[i][j]=max(dp[i][j]，dp[i][j-1])。
然后我们用前缀和数组sum预处理出区间[i,j]内1的数量，然后我们枚举每个区间如果当前区间能变成全0，就记录当前0的数量j-i+1对应的右边的1的数量dp[j+1][k-sum[j]+sum[i-1]]。
然后再将字符串颠倒，再求一遍就得到了连续1在0右边是最长0和最长1的对应关系，最后按照最开始所说的求最大值即可
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 3005;
string s;
int n, k;
int dp[N][N];
int ma[N];
int sum[N];
void init()
{//每次dp前初始化
for (int i = 0; i <= n; i++)
{
sum[i] = 0;
for (int j = 0; j <= n; j++)
{
dp[i][j] = 0;
}
}
}
void solve()
{
init();
for (int i = n - 1; i >= 0; i--)
{
if (i != n - 1)
{
for (int j = 0; j < n; j++)
{//大区间从小区间转移
dp[i][j] = dp[i + 1][j];
}
}
int cnt = 0;
for (int j = i; j < n; j++)
{
cnt += (s[j] == '0');
if (cnt > k)
{
break;
}
else
{//[i,n]区间能变成全1
dp[i][cnt] = max(dp[i][cnt], j - i + 1);
}
}
for (int j = 1; j <= k; j++)
{//操作数更大时候可以，更小时候也可以
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
}
}
ma[0] = dp[0][k];//整个字符串全变成1
for (int i = 0; i < n; i++)
{//预处理1的数量
sum[i] = sum[i - 1] + (s[i] == '1');
}
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (sum[j] - sum[i - 1] <= k)
{//对于每个连续0的数量，求出其对应的最大1的数量
ma[j - i + 1] = max(ma[j - i + 1], dp[j + 1][k - sum[j] + sum[i - 1]]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n >> k;
cin >> s;
for (int i = 0; i <= n; i++)
{
ma[i] = -1;
}
solve();//令0都在1左边求一遍
reverse(s.begin(), s.end());
solve();//令1都在0左边再求一遍
for (int i = 1; i <= n; i++)
{
int ans = 0;
for (int j = 0; j <= n; j++)
{
if (ma[j] != -1)
{//枚举最大值
ans = max(ans, i * j + ma[j]);
}
}
cout << ans << " ";
}
cout << endl;
}
return 0;
}