Codeforces Round 642 (Div. 3) E. K-periodic Garland（DP+前缀和）

题目链接

https://codeforces.com/contest/1353/problem/E

思路

令$dp[i][0/1]$分别表示第$i$个字符是$0$或者$1$时的前$i$个字符组成的花环所需的最少操作次数。

如果第$i$个字符变为$1$，分为两种情况：第一种情况是第$i-k$个字符必须为$1$，且$[i-k+1,i-1]$中间的字符必须为$0$。第二种情况是前$i-1$个字符全部为$0$。

如果第$i$个字符变为$0$，则前$i-1$个字符可以为$0$或$1$。

我们令$sum[i]$表示前$i$个字符中$1$的个数。

状态转移方程为：

$i-k\ge 0$时：$dp[i][1]=min(sum[i-1],dp[i-k][1]+(sum[i-1]-sum[i-k]))+(s[i]{\ne }^{\prime }{1}^{\prime })$

$i-k<0$时：$dp[i][1]=sum[i-1]+(s[i]{\ne }^{\prime }{1}^{\prime })$

$dp[i][0]=min(dp[i-1][0],dp[i-1][1])+(s[i]{\ne }^{\prime }{0}^{\prime })$

时间复杂度：$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 1e6 + 5, M = 5e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(time(0));

int n, k;
int sum[N], dp[N][2];
char s[N];
void solve()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i];
	}
	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + (s[i] == '1');
	}
	for (int i = 1; i <= n; i++)
	{
		dp[i][0] = dp[i][1] = inf;
	}
	for (int i = 1; i <= n; i++)
	{
		if (i - k >= 0)
			dp[i][1] = min(sum[i - 1], dp[i - k][1] + (sum[i - 1] - sum[i - k])) + (s[i] != '1');
		else dp[i][1] = (sum[i - 1]) + (s[i] != '1');
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] != '0');
	}
	cout << min(dp[n][0], dp[n][1]) << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}