hdu45221――小明系列问题――小明序列 线段树优化dp


小明系列问题――小明序列

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1918    Accepted Submission(s): 583

Problem Description
  大家都知道小明最喜欢研究跟序列有关的问题了,可是也就由于这样,小明几近已玩遍各种序列问题了。可怜的小明苦苦地在各大网站上寻觅着新的序列问题,可是找来找去都是自己早已研究过的序列。小明想既然找不到,那就自己来发明1个新的序列问题吧!小明想啊想,终究想出了1个新的序列问题,他欣喜若狂,由于是自己想出来的,因而将其新序列问题命名为“小明序列”。

  提起小明序列,他给出的定义是这样的:
  ①首先定义S为1个有序序列,S={ A1 , A2 , A3 , … , An },n为元素个数 ;
  ②然后定义Sub为S中取出的1个子序列,Sub={ Ai1 , Ai2 , Ai3 , … , Aim },m为元素个数 ;
  ③其中Sub满足 Ai1 < Ai2 < Ai3 < … < Aij⑴ < Aij < Aij+1 < … < Aim ;
  ④同时Sub满足对任意相连的两个Aij⑴与Aij都有 ij – ij⑴ > d (1 < j <= m, d为给定的整数);
  ⑤明显满足这样的Sub子序列会有许许多多,而在取出的这些子序列Sub中,元素个数最多的称为“小明序列”(即m最大的1个Sub子序列)。
  例如:序列S={2,1,3,4} ,其中d=1;
  可得“小明序列”的m=2。即Sub={2,3}或{2,4}或{1,4}都是“小明序列”。

  当小明发明了“小明序列”那1刻,情绪非常激动,以致于头脑混乱,因而他想请你来帮他算算在给定的S序列和整数d的情况下,“小明序列”中的元素需要多少个呢?

 

Input
  输入数据多组,处理到文件结束;
  输入的第1行动两个正整数 n 和 d;(1<=n<=10^5 , 0<=d<=10^5)
  输入的第2行动n个整数A1 , A2 , A3 , … , An,表示S序列的n个元素。(0<=Ai<=10^5)
 

Output
  请对每组数据输出“小明序列”中的元素需要多少个,每组测试数据输出1行。
 

Sample Input
      
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » hdu45221――小明系列问题――小明序列 线段树优化dp

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡