IT评测·应用市场-qidao123.com

标题: hdu7511 创作乐曲（口胡题解 线段树预处理+dp） [打印本页]

---

作者: 去皮卡多    时间: 2024-8-12 09:51
标题: hdu7511 创作乐曲（口胡题解 线段树预处理+dp）
标题

思路泉源

题解

一个暴力的想法，是求满足相邻项差值不超过k的子序列最大长度，然后用权值线段树二分，
复杂度是O(sumq nlogn)的，不能接受

然后思量优化掉这个logn的转移，
着实与泽与老师院赛那个题很像，求abs的最小值的dp，
其时转移是从前面>=a和<=a最接近的值转移
这个就是从前面第一个[a,a+k]和前面第一个[a-k,a]的值转移
预处理找到这些位置之后，每次现dp即可

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4