[luoguP2885] [USACO07NOV]电话线Telephone Wire（DP + 贪心）

传送门

真是诡异。

首先 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

上一篇：[luoguP1962] 斐波那契数列（矩阵快速幂）

下一篇：[luoguP3402] 最长公共子序列（DP + 离散化 + 树状数组）

---

DP 贪心 单调栈