Codeforces Round #587 (Div. 3) F. Wi-Fi - 线段树维护DP

有n个房子在x轴,房子的状态可以用0,1表示:
0:不可以安装路由器
1:可以安装路由器
每个房子可以直接连接到互联网。第i个房子代价为i。也可以安装路由器第i个房子代价为i。但是路由器可以使[i-k, i+k]都连上网,求出所有房子全部连上网需要的最小代价。
图片说明
图片说明

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

const int N=2e5+7;
const LL INF=1e18;

LL a[N], f[N][2];
struct SegTree {
    LL T[N<<2];
    SegTree () { memset(T,0x3f,sizeof(T)); }
    inline void pushup(int o) { T[o]=min(T[o<<1],T[o<<1|1]); }
    void add(int o,int l,int r,int pos,LL v){//修改 T[o]=v
        if(l==r) { T[o]=v; return; }
        int mid=l+r>>1;
        pos<=mid ? add(o<<1,l,mid,pos,v) : add(o<<1|1,mid+1,r,pos,v);
        pushup(o);
    }
    LL query(int o,int l,int r,int ql,int qr){//查询区间最大值

        if(l>qr||r<ql) return INF;
        if(l>=ql&&r<=qr) return T[o];
        int mid=l+r>>1; return min(query(o<<1,l,mid,ql,qr),query(o<<1|1,mid+1,r,ql,qr));
    }

}T1, T2;

int main(){

    memset(f, 0x3f, sizeof(f));
    int n, k; scanf("%d%d", &n, &k);
    for(int i=2; i<=n+1; i++){
        scanf("%1d", &a[i]);
    }

    f[1][1]=0; T2.add(1, 1, n+1, 1, min(f[1][0], f[1][1]));
    for(int i=2; i<=n+1; i++){
        f[i][0]=T1.query(1, 1, n+1, max(1, i-k), max(i-1, 1));
        if(a[i]==1){
            f[i][1]=T2.query(1, 1, n+1, max(1, i-k-1), max(i-1, 1))+i-1;
            T1.add(1, 1, n+1, i, f[i][1]);
        }
        else{
            f[i][1]=min(f[i-1][0], f[i-1][1])+i-1;
        }
        T2.add(1, 1, n+1, i, min(f[i][0], f[i][1]));
    }
    printf("%lld\n", min(f[n+1][0], f[n+1][1]));

    return 0;
}
全部评论

相关推荐

1.&nbsp;事件概述3月10日下午,华为在“心声社区”发布长达6500字通报,曝光72名正式员工及19名非雇员在非雇员招聘中存在徇私舞弊行为,多人出卖公司信息资产获利,引发热议。-&nbsp;“非雇员”一般指华为OD员工,与人力服务公司签劳动合同,以派遣方式到华为工作,薪资待遇与华为内部员工基本一致,可通过考核转正。2.&nbsp;相关传言与真相华为相关人士称暂无官方回应,很多传言细节不准确。&nbsp;华为成都研究所员工透露,此次通报主要涉及成都研究所的数据存储部门,整个数据存储业务约100余人,此次明文通报除名辞退或通报批评的有62名,“很多部门基本全开除”&nbsp;。网传任正非亲赴成都、封楼抓人等消息不实。早在2024年年中,就有...
七安有出处嘛:省流:任正非亲赴成都等消息不实,2024 年年中就有人举报了;涉及36名违规当事人,其中有13人被除名;10人有主动申报情节或情节较严重的,予以辞退处理;另有13人被劝退、个人职级降3等。另外还有26名相关管理责任人作为直接或间接管理者,被处以个人职级降6等,冻结个人涨薪、职级晋升、干部向上任命,冻结期6—12个月不等;若下属违规偶发,则仅通报批评。并没有释放100HC😂😂😂
点赞 评论 收藏
分享
云边有个小卖铺儿:校招生违约率低,所以我要高😂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务