题目：https://codeforces.com/contest/1216/problem/F
题意：一排有n个位置，我要让所有点都能联网，我有两种方式联网，第一种，我直接让当前点联网，花费为i，第二种，如果当前点的值为1，代表当前点可以放置一个路由器，范围 [i-k,i+k]都能连上网，花费为i，求最小花费是所有点都能连上网
思路：这个很容易看出是一个DP，我们设立dp[i],为前i个位置都能连上网的最小花费，因为设立一个路由器左右范围都可以联网，所以我们考虑设立路由器的右端点，如果i-k可以设立路由器，我们 dp[i]=min(dp[i],dp[j]+i-k) 但是我们这个j怎么确定呢，肯定是前面的最小值来的，我们在 [i-2*k-1,i] 里面寻找最小值，然后取最优 ，我们可以用单调队列求得最大值，用线段树也是可以的
#include<bits/stdc++.h> #define maxn 500005 #define mod 1000000007 using namespace std; typedef long long ll; deque<int> d; int n,k; char str[maxn]; ll dp[maxn]; int main(){ scanf("%d%d",&n,&k); scanf("%s",str+1); d.push_back(0);//必须加，因为我们设立第一个路由器的时候可能会用到0，但是第一个位置的值就是1了 for(int i=1;i<=n+k;i++){ dp[i]=dp[i-1]+i;//如果当前这个点用第一种方式联网的话 if(i-k>0&&str[i-k]=='1'){//如果可以用第二种方式联网 while(!d.empty()&&d.front()<i-2*k-1) d.pop_front(); //利用单调队列把不是该范围的数先踢出去 dp[i]=min(dp[i],dp[d.front()]+i-k);//因为是i-k这个位置设立路由器，所以+（i-k） } while(!d.empty()&&dp[d.back()]>=dp[i]) d.pop_back(); d.push_back(i); } ll mx= 0x3f3f3f3f3f3f3f3f; for(int i=n;i<=n+k;i++) mx=min(mx,dp[i]);//取最优 cout<<mx; }