3507专题

HDU 3507 [Print Article]DP斜率优化

题目大意 给定一个长度为\(n(n \leqslant 500000)\)的数列,将其分割为连续的若干份,使得 $ \sum ((\sum_{i=j}^kC_i) +M) $ 最小。其中\(C_i\)为序列中的项的值,\(M\)为常数。$ j,k $ 表示在原序列中连续的某一段的起始位置和结束位置。 解题思路 考虑到\(n\)的范围巨大,肯定不能用\(O(n^2)\)的暴力DP,而贪心又显然有问

#单调队列,动态规划,斜率优化#hdu 3507 Print Article

题目 一篇文章在打印k个需花费 m是常数,问最少花费多少就可以打完一篇文章 分析 对于 x 1 &lt; x x1&lt;x x1<x and x 2 &lt; x x2&lt;x x2<x 可得 d p [ x ] = d p [ x 1 ] + ( s u m [ x ] − s u m [ x 1 − 1 ] ) 2 + m dp[x]=dp[x1]+(sum[x]-sum[x