详细教程
https://www.cnblogs.com/orzzz/p/7885971.html
以下面的一道例题为例。
A.HDU 3507
给出 (N) 个单词，每个单词有个非负权值 (C_i) ，现要将它们分成连续的若干段，每段的代价为此段单词的权值和，还要加一个常数 (M) ，即 ((sum Ci)^2+M) 。现在想求出一种最优方案，使得总费用之和最小。 ((0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000))
解
首先考虑 (n^2) dp。
[sum[i]=sum_{j=1}^i C_j
]
[dp[i]=min(dp[j]+(sum[i]-sum[j])^2+M)
]
考虑如何优化。
设 (j_1>j_2) ，且 (j_1) 优于 (j_2) 。
有
[dp[j_1]+sum[i]^2+sum[j_1]^2-2*sum[i]*sum[j_1]+M<dp[j_2]+sum[i]^2+sum[j_2]^2-2*sum[i]*sum[j_2]+M$$
$$dp[j_1]+sum[j_1]^2-dp[j_2]-sum[j_2]^2<2*sum[i]*(sum[j_1]-sum[j_2])]
[2*sum[i]>frac{dp[j_1]+sum[j_1]^2-dp[j_2]-sum[j_2]^2}{sum[j_1]-sum[j_2]}
]