Special Subsequence

Time Limit: 5000ms
Memory Limit: 32768KB

This problem will be judged on ZJU. Original ID: 3349
64-bit integer IO format: %lld      Java class name: Main

There a sequence S with n integers , and A is a special subsequence that satisfies |Ai-Ai-1| <= d ( 0 <i<=|A|))

Now your task is to find the longest special subsequence of a certain sequence S

Input

There are no more than 15 cases , process till the end-of-file

The first line of each case contains two integer n and d ( 1<=n<=100000 , 0<=d<=100000000) as in the description.

The second line contains exact n integers , which consist the sequnece S .Each integer is in the range [0,100000000] .There is blank between each integer.

There is a blank line between two cases

Output

For each case , print the maximum length of special subsequence you can get.

Sample Input

5 2
1 4 3 6 5 5 0
1 2 3 4 5

Sample Output

3
1
 

Source

Author

CHEN, Zhangyi
 
解题:动态规划+线段树优化
 #include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int tree[maxn<<],Lisan[maxn],a[maxn],tot,n,d;
int query(int L,int R,int lt,int rt,int v){
if(lt <= L && rt >= R) return tree[v];
int mid = (L + R)>>,ret = ;
if(lt <= mid) ret = query(L,mid,lt,rt,v<<);
if(rt > mid) ret = max(ret,query(mid + ,R,lt,rt,v<<|));
return ret;
}
void update(int L,int R,int pos,int val,int v){
if(L == R){
tree[v] = max(tree[v],val);
return;
}
int mid = (L + R)>>;
if(pos <= mid) update(L,mid,pos,val,v<<);
if(pos > mid) update(mid + ,R,pos,val,v<<|);
tree[v] = max(tree[v<<],tree[v<<|]);
}
int main(){
while(~scanf("%d%d",&n,&d)){
memset(tree,,sizeof tree);
for(int i = ; i < n; ++i){
scanf("%d",a + i);
Lisan[i] = a[i];
}
sort(Lisan,Lisan + n);
tot = unique(Lisan,Lisan + n) - Lisan;
int ret = ;
for(int i = ; i < n; ++i){
int L = max(,(int)(lower_bound(Lisan,Lisan + tot,a[i] - d) - Lisan + ));
int R = min(tot,(int)(upper_bound(Lisan,Lisan + tot,a[i] + d) - Lisan));
int tmp = ,pos = lower_bound(Lisan,Lisan + tot,a[i]) - Lisan + ;
if(L <= R) tmp = query(,tot,L,R,) + ;
ret = max(ret,tmp);
update(,tot,pos,tmp,);
}
printf("%d\n",ret);
}
return ;
}

最新文章

  1. Linux入门50指令
  2. atitit.设计模式(2) -----查表模式/ command 总结
  3. 关于eclipse android 在manifest改app应用包名注意事项
  4. sqlalchemy 的 ORM 与 Core 混合方式使用示例
  5. lightoj 1015
  6. Adobe After Effect CC2017 for Mac
  7. nginx try_files 详解
  8. Java包装类及其拆箱装箱
  9. IIS发布的网站常见的问题汇总
  10. 【STL】vector的insert方法详解
  11. DROP语句总结
  12. 嵌套的 ajax 请求
  13. Jmeter在命令行运行技巧
  14. python requests 设置headers 和 post请求体x-www-form-urlencoded
  15. #leetcode刷题之路28-实现 strStr() 函数
  16. 通过Nrgok映射外网调试微信
  17. bzoj1954 The xor-longest path
  18. 面试准备5之rest-framework部分
  19. SpringBoot非官方教程 | 第十一篇:springboot集成swagger2,构建优雅的Restful API
  20. python数据之间的转换和关系

热门文章

  1. ViewModel、ViewData、ViewBag、TempData、Session之间的区别和各自的使用方法
  2. HTML5移动Web开发
  3. ECMA里面的一元符
  4. POJ 2187 凸包+旋转卡壳
  5. 思维/构造 HDOJ 5353 Average
  6. jmeter生成时间的函数
  7. 重新学习Java——Java基本的程序设计结构(二)
  8. html5前端杂记
  9. Appium基于python unittest自动化测试并生成html测试报告
  10. 联想 S5 Pro(L78041)免解锁BL 免rec 保留数据 ROOT Magisk Xposed 救砖 ZUI 5.0.123