题目:给出一个序列,找出一个最长的子序列,相邻的两个数的差在d以内。

 /*
线段树优化dp
dp[i]表示前i个数的最长为多少,则dp[i]=max(dp[j]+1) abs(a[i]-a[j])<=d
复杂度为O(n ^ 2)
利用线段树优化,线段树保存区间最大值。离散化后便可求出,还要注意 对于叶子节点保存的即为dp的值,每次更改即可,开始一直累加。。。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std;
#define lson l,m,rt<<1
#define rson m + 1, r, rt<<1|1
const int maxn = 1e5 + ;
int s[maxn];
int n, d;
int san[maxn], tot;
int sum[maxn << ];
void pushUp(int rt){
sum[rt] = max(sum[rt<<], sum[rt<<|]);
}
void update(int pos, int c, int l, int r, int rt){
if (l == r){
sum[rt] = c;//注意
return ;
}
int m = (l + r) >> ;
if (pos <= m) update(pos, c, lson);
else update(pos, c, rson);
pushUp(rt);
}
int query(int L, int R, int l, int r, int rt){
if (L <= l && R >= r){
return sum[rt];
}
int m = (l + r) >> ;
int ret = ;
if (L <= m) ret = query(L, R, lson);
if (R > m) ret = max(ret, query(L, R, rson));
return ret;
}
int main(){
while (~scanf("%d%d", &n, &d)){
tot = ;
for (int i = ; i <= n; ++i){
scanf("%d", &s[i]);
san[tot++] = s[i];
}
sort(san, san + tot);
tot = unique(san, san + tot) - san; memset(sum, , sizeof(sum));
int ans = ;
for (int i = ; i <= n; ++i){
int pos = lower_bound(san, san + tot, s[i]) - san + ;
int l = lower_bound(san, san + tot, s[i] - d) - san + ;
int r = upper_bound(san, san + tot, s[i] + d) - san;
int que = query(l, r, , tot, ) + ;
//cout << " l = " << l << " r = " << r << endl;
ans = max(ans, que);
//cout << " ans = " << ans << endl;
update(pos, que, , tot, );
}
printf("%d\n", ans);
}
return ;
}

最新文章

  1. C++ 中静态成员函数访问非静态成员变量的方法
  2. iOS - 沙盒中,如何判断存在文件、目录
  3. mq_close
  4. 教程-隐藏/显示任务栏-程序不在任务显示-全面控制Windows
  5. php学习之道:php中soap的使用实例以及生成WSDL文件,提供自己主动生成WSDL文件的类库——SoapDiscovery.class.php类
  6. Theos 工程make package时报错
  7. 为jEasyUi的日期控件添加一个“清空”按钮----通过修改1.4的easyui.min.js
  8. JFinal极速开发框架使用笔记(二) 两个问题,一个发现
  9. 关于Keychain
  10. Centos 32位 安装 NodeJS
  11. 前后端分离djangorestframework——路由组件
  12. npm install 错误 安装 chromedriver 失败的解决办法
  13. Struts2之ValueStack、ActionContext
  14. 基于SimpleChain Beta的跨链交互与持续稳态思考
  15. BZOJ4999: This Problem Is Too Simple!树链剖分+动态开点线段树
  16. UVa 11178 Morley&#39;s Theorem (几何问题)
  17. static &amp; abstract
  18. windows安装mysql-5.7压缩版详细教程
  19. git提交代码到码云
  20. 在Linux上编译使用tcmalloc

热门文章

  1. 倍福TwinCAT(贝福Beckhoff)常见问题(FAQ)-如何把FBD功能块转换成ST语言
  2. 【Python3 爬虫】05_安装Scrapy
  3. 使用 curl() 函数实现不同站点之间注册用户的同步
  4. spring事务管理源码解析--加了@Transactional注解后Spring究竟为我们做了哪些事情?
  5. NIO之DatagramChannel
  6. Atitit.java&#160;jar&#160;hell解决方案-----Djava.ext.dirs&#160;in&#160;ide&#160;envi..
  7. 关于python ide
  8. android-studio于java相关
  9. js中级系列三:前端性能优化
  10. SpringMVC请求使用@PathVariable获取文件名称并且文件名中存在.导致路径被截取的问题