题意：给定一个字符串s 现在让你用最小的花费 覆盖所有区间
思路：dp[i]表示前i个全覆盖以后的花费 如果是0 我们只能直接加上当前位置的权值 否则 我们可以区间询问一下最小值 然后更新
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int N = 2e5+7;
typedef long long ll;
const ll mod = 998244353;
using namespace std;
ll dp[N];
ll a[N],sum[N];
struct tree{
int l,r;
ll v;
int po;
}t[N<<4];
int nico=0;
void build(int p,int l,int r){
t[p].l=l; t[p].r=r; t[p].v=inf;
if(l==r){
t[p].po=l;
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void update(int p,int x,ll v){
if(t[p].l==t[p].r){
t[p].v=v;
return ;
}
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) update(p<<1,x,v);
else update(p<<1|1,x,v);
if(t[p<<1].v<t[p<<1|1].v){
t[p].v=t[p<<1].v;
t[p].po=t[p<<1].po;
}else{
t[p].v=t[p<<1|1].v;
t[p].po=t[p<<1|1].po;
}
}
tree query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p];
}
int mid=(t[p].l+t[p].r)>>1;
tree res1,res2;
if(l>mid){
return query(p<<1|1,l,r);
}else if(r<=mid){
return query(p<<1,l,r);
}else{
res1=query(p<<1,l,r);
res2=query(p<<1|1,l,r);
if(res1.v<res2.v){
return res1;
}else{
return res2;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n,k; cin>>n>>k;
string s; cin>>s;
build(1,0,n);
update(1,0,0);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+i;
}
int mi=inf;
for(int i=n-1;i>=0;i--){
if(s[i]=='1'&&i!=n-1){
s[min(i+k,n-1)]='1';
s[i]='0';
if(i+k>=n-1){
mi=min(mi,i)+1;
}
}
}
if(s[n-1]=='1'&&mi==inf){
mi=n;
}
// cout<<s<<endl;
for(int i=1;i<=n;i++){
if(s[i-1]=='1'){
if(i==n){
tree res=query(1,max(mi-k-1,0),i-1);
dp[i]=res.v+mi;
// dp[i][0]=min(dp[i-1][0],dp[i-1][1])+mi;
}else{
tree res=query(1,max(i-2*k-1,0),i-1);
dp[i]=res.v+i-k;
// dp[i][0]=min(dp[i-1][0],dp[i-1][1])+i-k;
}
}else{
dp[i]=dp[i-1]+i;
// dp[i][0]=inf;
}
update(1,i,dp[i]);
}
cout<<dp[n]<<endl;
return 0;
}