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 doubletypedef 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;
}