题目：

题意：一排有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
     
      #define maxn 500005#define mod 1000000007using namespace std;typedef long long ll;deque
      
        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()
       
        =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<