首页 > 其他 > 详细

斜率优化DP

时间:2019-01-12 10:26:39      阅读:56      评论:0      收藏:0      [点我收藏+]

标签:价值   状态   clas   noi   hnoi2008   www   class   mark   lin   

斜率优化DP

模型:\(f_i = min { f_j+w_{i,j} }\)
感觉不太对劲.....跟斜率好像关系不太大

[HNOI2008]玩具装箱TOY

只做了这一道题.

考虑\(i\)这个点.设状态\(f[i]\)表示以i结尾的费用最小.

转移式子:

\(f[i] = min{ f_j + (i - j + \sum_{k=j}^i C_k) ^ 2 }\)

比较\(j,k\)的价值(至于为什么会比较,看完下面的推式子就明白了

此处省略式子....(懒得用markdown 打了

\(s_i = \sum_i + i,C= L+1\)

推成式子就是\(S_i >= \frac{f_k + (s_k + C)^2 - f_j - (s_j + C)^2}{2 * (s_k - s_j)}\)

让式子左边全是关于\(i\)的,且式子右边不含有\(i\)

\(S_i\) ** 只有是单调的才可以用斜率优化 **

然后用个单调队列维护一下就做完了...

斜率优化DP

标签:价值   状态   clas   noi   hnoi2008   www   class   mark   lin   

原文:https://www.cnblogs.com/gzygzy/p/10258572.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号