1.题目相关
-
标签：
DP斜率优化 - 题目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1010
- 题目大意：中文题。
2.思路
DP方程比较容易得到。
其中：
改写一下形式：
若决策 j 比决策 k 更优 ：
根据斜率优化DP的模板（注意根据斜率形式的大于小于，相应的改变程序）
for (int i = 1; i <= n; i++) {
while (h < t && slope(q[h], q[h+1]) < "...") h++;
f[i] = "...";
while (h < t && slope(q[t-1], q[t]) > slope(q[t], i)) t--; q[++t]=i;
}
本题就可以较好的解决了。
