树状数组优化dp——cf985E经典
2024-09-06 06:02:59
/*
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]<=d
即可以把[j+1,i+1]分为一组,放在前j个之后 先进行排序,暴力的复杂度是o(n*n)
其实每次求dp[i]时,只要考虑区间[pos,i-k]的dp即可,pos为第一个比a[i]-d小的坐标再-1(为什么要-1,因为新的段是接在前面的段后面,所以其实是从a[i]-d的前面开始算起)
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 5000005 int d,dp[maxn],a[maxn],n,k; int bit[maxn];
void update(int x,int v){
while(x<=n){
bit[x]+=v;
x+=(x&-x);
}
}
int query(int x){
int res=;
while(x){
res+=bit[x];
x-=(x&-x);
}
return res;
} int main(){
cin>>n>>k>>d;
for(int i=;i<=n;i++)cin>>a[i];
sort(a+,a++n); for(int i=;i<=n;i++){
if(i<k)dp[i]=;
else if(a[i]-a[]<=d)dp[i]=;
else {
int pos=lower_bound(a+,a++n,a[i]-d)-a-;//这里要注意一下
dp[i]=(query(i-k)-query(pos-))>;
}
if(dp[i])update(i,);
}
if(dp[n])puts("YES");
else puts("NO");
}
最新文章
- 为什么你不应该使用 MongoDB
- MySQL性能优化的最佳经验,随时补充
- oracle 常见恢复
- macbook 我们需要买吗
- Training little cats_矩阵快速幂
- boost 编译
- 排序算法(冒泡,选择,快速)Java 实现
- Excel操作 Microsoft.Office.Interop.Excel.dll的使用
- 初涉JavaScript模式系列 阶段总结及规划
- iOS 删除相册中照片--来自简书
- CentOS服务器上的 git 包版本控制
- CopyOnWriteArrayList集合排序异常问题
- vim美化基本配置
- 提取C3D视频特征(官方文档&;实践)
- Oracle 使用序列实现自增列 及重置序列
- layer 关闭当前弹出层
- CentOS卸载通过yum安装的软件
- MFS故障测试及维护总结
- 如何使用网格搜索来优化深度学习模型中的超参数(Keras)
- unigui如何连接数据库