A.HDU - 3507 Print Article
题意
就是输出序列a[n],每连续输出的费用是连续输出的数字和的平方加上常数M
让我们求这个费用的最小值。
题解
概率DP的入门题,把我搞得要死要活的。
首先dp[i]表示输出前i个的最小费用 很简单得得出一个方程
其中sum[i]表示数字的前i项和,但是这个方程的复杂度是n^2 所以这时候就要用到斜率优化 ,ps:个人感觉斜率DP都用到了队列,来把前面绝对不优秀的项都出队,这样每次运算都只要在队列中找就行,而且每个元素只有一次出队和入队 所以复杂度只有N
首先假设在算dp[i]的 ,k<j<i,并且J点比K点优秀
那么
对上面方程分解整理得:
注意正负号,不然会影响不等号的方向
另
于是上面的式子变成斜率表达式
由于不等式右边的sum[i]随着i的增加而递增
所以我们另
1.如果上面的不等式成立 说明J比K优,而且随着i的增加上述不等式一定是成立的,也就是对于以后的i来说J都比K优秀,所以K是可以淘汰的
2.如果
那么J是可以淘汰的
假设g[I,J]<sum[i] 就是I比J优秀,那么J就没存在的价值
相反,如果g[I,J]>sum[i] 那么同样有g[J,K]>sum[I] 那么K比J优秀 所以J是可以淘汰的
所以这样相当于维护一个下凸的图形,斜率在增加,用队列维护
ps:以上都是抄bin巨的博客
1 |
|