网站首页
编程语言
数据库
系统相关
其他分享
编程问答
pht
2024-10-25
一种巧妙的DP优化方法——pht转化
P6944[ICPC2018WF]GemIsland之前一直都没有弄懂pht转化有什么用,现在懂了,故作文以记之。直接从CYJ的题解开始讲起,这种阶梯DP是人都想得出来,只不过是\(O(n^4)\)或者\(O(n^3ln(n))\)的,本人觉得这道题的关键在于如何优化掉整整一个\(O(n)\)首先一个数列的权值就是类似于