首页 > 代码库 > [luoguP2885] [USACO07NOV]电话线Telephone Wire（DP + 贪心）
[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[i-1][j+]更新，又可以从f[i-1][j]更新，还可以从f[i-1][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 { 9 return x < y ? x : y;10 }11 12 int main()13 {14 int i, j;15 scanf("%d %d", &n, &c);16 for(i = 1; i <= n; i++) scanf("%d", &a[i]);17 for(i = 1; i <= n; i++)18 {19 temp = INF;20 for(j = 100; j >= a[i]; j--)21 {22 temp = min(temp + c, f[i - 1][j]);23 f[i][j] = temp + (j - a[i]) * (j - a[i]);24 }25 temp = INF;26 for(j = 1; j <= 100; j++)27 {28 temp = min(temp + c, f[i - 1][j]);29 f[i][j] = min(f[i][j], temp + (j - a[i]) * (j - a[i]));30 if(j < a[i]) f[i][j] = INF;31 }32 }33 for(i = a[n]; i <= 100; i++) ans = min(ans, f[n][i]);34 printf("%d\n", ans);35 return 0;36 }
[luoguP2885] [USACO07NOV]电话线Telephone Wire（DP + 贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。