传送门
真是诡异。
首先 O(n * 100 * 100)
三重循环
f[i][j] 表示到第 i 个柱子，高度是 j 的最小花费
f[i][j] = min(f[i 1][k] + abs(k j) * c + (j a[j]) * (j a[j]) (1 <= k <= 100)
然而肯定超时
对于f[i][j]的值，既可以从f[i1][j+]更新，又可以从f[i1][j]更新，还可以从f[i1][j]更新。
所以可以从后往前扫，从前往后扫，都记录一个前缀最小值，然后用这个更新就行。
——代码
1 #include <cstdio> 2 3 const int MAXN = 100001, INF = 100000001; 4 int n, c, temp, ans = INF; 5 int a[MAXN], f[MAXN][101]; 6 7 inline int min(int x, int y) 8 11 12 int main() 13 25 temp = INF; 26 for(j = 1; j <= 100; j++) 27 32 } 33 for(i = a[n]; i <= 100; i++) ans = min(ans, f[n][i]); 34 printf("%d\n", ans); 35 return 0; 36 }View Code
上一篇：[luoguP3402] 最长公共子序列（DP + 离散化 + 树状数组）
下一篇：[luoguP1130] 红牌（DP）
DP 贪心 单调栈
