树状数组优化dp——cf985E经典
标签：复杂度 条件 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
评论