CF1216F Wi-Fi

CF1216F Wi-Fi

题意

给定 $n,k$，和一个长度为 $n$ 的 01 序列 $\{s\}$。我们需要把一个长度为 $n$ 空白区间染色，你有如下两种操作：

1. 对点 $i$ 单点染色，代价为 $i$。
2. 若点 $i$ 满足 $s_i$ 为 1，对 $[i-k,i+k]$ 区间染色，代价为 $i$。

求把空白区间全部染色的最小代价。

Sol

令 $dp_i$ 表示恰好将区间 $[1,i]$ 染色的最小代价，考虑两种操作对 dp 状态的转移，即：

1. 第一种直接从 $dp_{i-1}$ 予以转移：$dp_{i} = dp_{i-1} + i$。
2. 第二种则从 $dp_{j},j\in[i-2\times k-1,i-1]$ 转移，$dp_{i} = \min \{ dp_{j} \} + h(j)$，其中 $h(j)$ 表示 $j$ 的定义域内使得 $s_j$ 为 1 成立的最小值。

由于是求最值，我们可以考虑单调队列优化转移。

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

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e5+1e1;
const lint INF=1e18+1e9;

lint dp[MAXN];
int q[MAXN],Q[MAXN],n,k,Head,Tail,l,r;
string s;

int main(void){

	cin>>n>>k>>s;
	q[Tail++]=0;
	for(int i=1;i<=n;i++){
		dp[i]=dp[i-1]+i;
		if(s[i-1]=='1') Q[r++]=i;
		while(l<r && Q[l]+k<i) ++l;
		while(Head<Tail && q[Head]+k+k+1<i) ++Head;
		if(l<r){
			while(Head<Tail && q[Head]+k+1<Q[l]) ++Head;
			dp[i]=min(dp[q[Head]]+Q[l],dp[i]);
		}
		while(Head<Tail && dp[q[Tail-1]]>=dp[i]) --Tail;
		q[Tail++]=i;
	}
	printf("%lld\n",dp[n]);

	return 0;
}