小明系列问题――小明序列
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)
输入的第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
波比源码 » hdu45221――小明系列问题――小明序列 线段树优化dp
