[BZOJ1010]玩具装箱
由于今天考到了斜率优化(大雾)然而不会做,所以就重新开始学习dp的优化了,首先学习的是1D1D的决策单调ovo,去写了一道裸题,我看lyzyA过的代码觉得人生无望,为什么他写斜率优化要比我写决策单调的那个队列代码要短那么多那么多那么多哼!
决策单调的意思就是dp[i]取得最优值的位置>=dp[k]的取得最优值的位置,k<i。但是并不能直接拿着上一次决定的最优值开始for,因为万一全部决策都是1就T穿了,ovo因为之前一直都是这样想的所以提醒一下自己(果然是太naive了),运用一个队列就可以搞定啦,每次去找这个决策能够起作用的区间,感觉那个1D1D动态规划也讲的很清楚了,就不赘述了。
至于为什么是决策单调的?打表可得>_<
上面这个是论文的地址。
然后粘一下这道题的code:https://paste.ubuntu.net/15327017/
然后似乎土地购买也是决策单调,那就合在一起好了XDD
https://paste.ubuntu.net/15327193/
我写出来的决策单调似乎都是一个味道,不管啦自己yy的代码丑是丑了点。