CF1353E K-periodic Garland

由题意，每个位置上有且只有 \(0/1\) 两种状态，且我们若是求出前缀和就能快速得出其中某一段中 \(1\) 的个数。

首先看一下如果让我们构造怎么构造。我们要构造一个 \(1\) 之间距离恰好为 \(k\) 的序列，就是说位置上的状态每次转移到 \(1\) ，都必须转移回到 \(0\) ，在 \(0\) 的状态呆 \(k\) 次再转移回 \(1\) 状态。

画出状态机如下：

由这个图我们先得出一个暴力且错误的状态转移方程：

\(f(i)=f(i-k)+sum(i-1)-sum(i-k)+[s_i=0]\)，其中\(f(i)\) 表示构造第一位是 \(1\) 的序列需要改造的步数 ，\(sum\) 是原来序列的前缀和，\(s_i\) 是原序列。

这个东西为什么错误？因为我们不敢说第一位一定是 \(1\)，说不定答案的序列开头很长一段都是 \(0\)。我们首先想到，这个问题可以大力枚举前面 \(0\) 的位数解决。假设我们把前 \(i-1\) 位设为 \(0\)，第 \(i\) 位设成 \(1\) 的代价为 \(g(i)\)，我们很容易得到：\(g(i)=sum(i-1)+[s_i=0]\)。

我们修改状态 \(f(i)\) 为到第 \(i\) 位为 \(1\) 时，前面均合法且至少有一个 \(1\) 的最小代价。

那么我们可以得到状态转移方程：\(f(i)=min(\ f(i-k),\ g(i-k)\ )+sum(i-1)-sum(i-k)+[s_i=0]\)。

我们的后缀仍然有可能全是 \(0\) ，所以统计答案时，我们枚举构造序列长度 \(i\) ，同时维护一个值 \(z\) 表示将以 \(i+1\) 为起点的后缀全部设为 \(0\) 的代价。答案就是 \(Min_{i=1}^nmin(\ f(i)\ ,\ g(i)\ )+z(i)\)

个人感觉难度 绿-蓝

#include <bits/stdc++.h>
using namespace std;

const int N=4e6+10;
int f[N],g[N],sum[N];
char str[N];

int main()
{
	int t; cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k>>(str+1);
		for(int i=0;i<=n;i++) f[i]=0x3f3f3f3f,sum[i]=0;
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+(str[i]-'0'), g[i]=sum[i-1]+int(str[i]=='0');
		for(int i=1;i<=n;i++)
			if(i>k) f[i]=min(f[i-k],g[i-k])+sum[i-1]-sum[i-k]+int(str[i]=='0');
		int ans=sum[n];
		for(int i=1;i<=n;i++)
			ans=min(ans,min(f[i],g[i])+sum[n]-sum[i]);
		cout<<ans<<'\n';
	}
	return 0;
}