F. Wi-Fi(线段树实现dp)

题：http://codeforces.com/contest/1216/problem/F

dp[i][0]:表示第i个位置不装的最小代价

dp[i][1]:表示第i个位置装的最小代价

T1的线段树是维护装的最小代价

T2的线段树是维护装和不装的最小代价

#include<bits/stdc++.h>
using namespace std;
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
typedef long long ll;
const int M=2e5+5;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll dp[M][2];
char s[M];
struct node{
    ll tree[M<<2];
    T(){memset(tree,INF,sizeof(tree));}
    void up(int root){
        tree[root]=min(tree[root<<1],tree[root<<1|1]);
    }
    void update(int pos,ll val,int root,int l,int r){
        if(l==r){
            tree[root]=min(tree[root],val);
            return ;
        }
        int midd=(l+r)>>1;
        if(pos<=midd)
            update(pos,val,lson);
        else
            update(pos,val,rson);
        up(root);
    }
    ll query(int L,int R,int root,int l,int r){
        if(L<=l&&r<=R){
            return tree[root];
        }
        int midd=(l+r)>>1;
        ll ans=INF;
        if(L<=midd)
            ans=min(ans,query(L,R,lson));
        if(R>midd)
            ans=min(ans,query(L,R,rson));
        return ans;
    }
}T1,T2;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    scanf("%s",s+2);
    memset(dp,INF,sizeof(dp));
    memset(T1.tree,INF,sizeof(T1.tree));
    memset(T2.tree,INF,sizeof(T2.tree));
    dp[1][0]=dp[1][1]=0;
  //  cout<<dp[2][1]<<endl;
    T2.update(1,0,1,1,n);
    for(int i=2;i<=n+1;i++){
        dp[i][0]=T1.query(max(1,i-k),i-1,1,1,n);
        if(s[i]=='1')
            dp[i][1]=T2.query(max(1,i-k-1),i-1,1,1,n)+i-1;
        else
            dp[i][1]=min(min(dp[i-1][0],dp[i-1][1]),T1.query(max(1,i-k-1),i-1,1,1,n))+i-1;
        T2.update(i,min(dp[i][0],dp[i][1]),1,1,n);
        if(s[i]=='1')
            T1.update(i,dp[i][1],1,1,n);
    }
    printf("%I64d\n",min(dp[n+1][0],dp[n+1][1]));
    return 0;
}

View Code