D. Trees and Segments Codeforces Round 893 (Div. 2)

Problem - D - Codeforces

题目大意：给出一个长度为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
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;
}