CF1353E K-periodic Garland 题解

分析

考虑 DP。

定义状态函数 \(f_i\) 表示处理完前 \(i\) 个字符且第 \(i\) 个字符为 \(1\) 时的最小代价。则对于 \(i\)，有两种情况：

1. \(i\) 不是第一个 \(1\)，则上一个 \(1\) 的位置必定为 \(i-k\)。
2. \(i\) 是第一个 \(1\)，没有上一个 \(1\)。

得到转移方程：\(f_i = \min (f_{\max(0,i-k)}+w(\max(0,i-k),i-1),w(0,i-1))+[c_i \ne 1]\)。其中 \(w(l,r)\) 表示 \([l,r]\) 中 \(1\) 个数量，也就是将区间全部变成 \(0\) 的最小代价。

对于答案，枚举最后一个 \(1\) 的位置，然后后面的 \(1\) 全部变成 \(0\)。即 \(ans= \min\limits_{i=0}^{n}f_i+w(i+1,n)\)。

复杂度 \(O(n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
	il int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
		return x*f;
	}
	il int qmi(int a,int b,int p){
		int ans=1;
		while(b){
			if(b&1) ans=ans*a%p;
			a=a*a%p,b>>=1;
		}
		return ans;
	}
	il auto max(auto a,auto b){return (a>b?a:b);}
	il auto min(auto a,auto b){return (a<b?a:b);}
	il int gcd(int a,int b){
		if(!b) return a;
		return gcd(b,a%b);
	}
	il int lcm(int a,int b){
		return a/gcd(a,b)*b;
	}
	il void exgcd(int a,int b,int &x,int &y){
		if(!b) return x=1,y=0,void(0);
		exgcd(b,a%b,x,y);
		int t=x;
		x=y,y=t-a/b*x;
		return ;
	}
	mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=1e6+10;
int n,k;
int f[N],s[N];
char c[N];

il int w(int l,int r){
	if(l>r) return 0;
	return s[r]-s[l-1];
}

il void solve(){
	n=rd,k=rd,scanf("%s",c+1);
	for(re int i=1;i<=n;++i) s[i]=s[i-1]+c[i]-'0';
	int ans=1e9+7;
	for(re int i=1;i<=n;++i)
		f[i]=min(f[max(0*1ll,i-k)]+w(max(0*1ll,i-k)+1,i-1),f[0]+w(1,i-1))+(c[i]!='1');
	for(re int i=0;i<=n;++i)
		ans=min(ans,f[i]+w(i+1,n));
	printf("%lld\n",ans);
	return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int t=rd;while(t--)
	solve();
	return 0;
}