【DP】E. K-periodic Garland

E. K-periodic Garland

题意：给定长度为n的01字符串，每次操作可以改变一个字符的状态，问使字符串中相邻1的距离为k的最小操作次数

思路：

DP。

(pre[i])记录前(i)项中(1)的个数

(dp[i][0])为使得前(i)项都合法，第(i)位为(0)时的最小操作次数

(dp[i][1])为使得前(i)项都合法，第(i)位为(1)时的最小操作次数

那么转移方程

$dp[i][0]=min(dp[i-1][0],dp[i-1][1])+(s[i]==1) $

因为第(i)项为(0)时对合法性无影响，其合法性可以直接从(dp[i-1][0]或者dp[i-1][1])转移过来，操作次数更新由(s[i]==1)负责，若(s[i])本身就为0，则新增0次操作，否则新增1次操作

(dp[i][1]=min(dp[i-k][1]+pre[i-1]-pre[i-k],pre[i-1])+(s[i]==0))

当第(i-k)项合法时，要使第(i)项为(1)时合法，则要保证第(i-k+1)项到第(i-1)项都为(0)，第(i)项才能为(1)（此时(pre[i-1]-pre[i-k]=0)），(dp[i][1])的状态才能从(dp[i-k][1])转移过来；或者从“令(1)到(i-1)项全为(0)，使得第(i)项为整个序列的第一个(1)”的状态转移过来。操作次数更新由(s[i]==0)负责，若(s[i])本身就为1，则新增0次操作，否则新增1次操作

最后注意输入的是字符数组

void solve() {
	int n, k;
	cin >> n >> k;
	cin >> s+1;
	for (int i = 1; i <= n; i++)
		pre[i] = pre[i - 1] + (s[i] == '1');
	for (int i = 1; i <= n; i++) {
		int p = max(0, i - k);
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == '1');
		dp[i][1] = min(dp[p][1] + pre[i - 1] - pre[p], pre[i - 1]) + (s[i] == '0');
	}
	cout << min(dp[n][0], dp[n][1]) << endl;
	for (int i = 0; i <= n; i++) {
		dp[i][1] = 0;
		dp[i][0] = 0;
		pre[i] = 0;
	}
}