当前位置 : 主页 > 网页制作 > css >

CF contest 1216 Div3. F

来源:互联网 收集:自由互联 发布时间:2021-06-13
题目链接:Click here Solution: 看起来是贪心,其实不然。。。 我们定义 \(f[i]\) 表示 仅 覆盖 \(1\sim i\) 所需要的最小代价,那么对 \(i\) 为0的点来说,易得 \(f[i]=min(f[i],f[i-1]+i)\) 考虑当 \(

题目链接:Click here

Solution:

看起来是贪心,其实不然。。。

我们定义\(f[i]\)表示覆盖\(1\sim i\)所需要的最小代价,那么对\(i\)为0的点来说,易得\(f[i]=min(f[i],f[i-1]+i)\)

考虑当\(i\)为1时怎么办,当\(i\)为1时,根据定义,我们不转移\(i\)这个位置的值,而转移\(i+k\)这个位置的值

很显然,只要\(1 \sim p(i-k\le p\le i+k-1)\)已被覆盖,那么再选\(i\)\(1\sim i+k\)就能够被覆盖

则我们用线段树维护区间\(f\)最小值,每次转移找最小值转移即可。最后注意判断边界情况。

Code:

#include<bits/stdc++.h>
#define ls q<<1
#define rs q<<1|1
#define int long long
using namespace std;
const int N=2e5+1;
const int maxn=1e15;
char s[N];
int n,k,f[N],mn[N<<2];
int min(int a,int b){return b<a?b:a;}
int max(int a,int b){return b<a?a:b;}
void update(int q){mn[q]=min(mn[ls],mn[rs]);}
void ins(int q,int l,int r,int x,int v){
    if(l==r) return mn[q]=v,void();
    int mid=l+r>>1;
    if(mid>=x) ins(ls,l,mid,x,v);
    else ins(rs,mid+1,r,x,v);
    update(q);
}
int query(int q,int l,int r,int L,int R){
    if(R<L) return 1e18;
    if(l>=L&&r<=R) return mn[q];
    int mid=l+r>>1,re=maxn;
    if(mid>=L) re=min(re,query(ls,l,mid,L,R));
    if(mid<R) re=min(re,query(rs,mid+1,r,L,R));
    return re;
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    n=read(),k=read();
    scanf("%s",s+1);
    memset(mn,127,sizeof(mn));
    memset(f,127,sizeof(f));f[0]=0;
    for(register int i=1;i<=n;i++){
        if(s[i]=='1'){
            int p=min(n,i+k);
            int v=query(1,1,n,max(1,i-k-1),p-1);
            if(i-k-1<=0) f[p]=min(f[p],i);
            f[p]=min(f[p],v+i);ins(1,1,n,p,f[p]);
        }else f[i]=min(f[i],f[i-1]+i),ins(1,1,n,i,f[i]);
    }
    printf("%lld\n",f[n]);
    return 0;
}
网友评论