树状数组优化dp——cf985E经典

2020-12-13 06:10

阅读：217

标签：复杂度条件 def turn upd ace main include 经典

/*
dp[i]=0|1 表示前i是否可以被成功分组， 
dp[i+1]能够变成1的三个条件
1：j∈[0,i-k]里存在dp[j]=1 
2：dp[j]=1
3：a[i+1]-a[j+1]*/
#includeusing namespace std;
#define maxn 5000005
    
int d,dp[maxn],a[maxn],n,k;
    
int bit[maxn];
void update(int x,int v){
    while(xn){
        bit[x]+=v;
        x+=(x&-x);
    }
}
int query(int x){
    int res=0;
    while(x){
        res+=bit[x];
        x-=(x&-x);
    }
    return res;
}

int main(){
    cin>>n>>k>>d;
    for(int i=1;i>a[i];
    sort(a+1,a+1+n);
    
    for(int i=1;i){            
        if(i0;
        else if(a[i]-a[1]1;
        else {
            int pos=lower_bound(a+1,a+1+n,a[i]-d)-a-1;
            dp[i]=(query(i-k)-query(pos-1))>0;
        }
        if(dp[i])update(i,1);
    }
    if(dp[n])puts("YES");
    else puts("NO");
}

树状数组优化dp——cf985E经典

标签：复杂度条件 def turn upd ace main include 经典

原文地址：https://www.cnblogs.com/zsben991126/p/11169130.html

上一篇：js事件之神奇的onclick

下一篇：JavaScript 创建DIV 设置样式不起作用，很多都是因为设置样式的顺序问题

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：树状数组优化dp——cf985E经典
文章链接：http://soscw.com/index.php/essay/32619.html

亲，登录后才可以留言！

树状数组优化dp——cf985E经典

评论

热门文章

推荐文章

最新文章

置顶文章