题目传送门(BZOJ)
>原文链接<

题解 :

状态 :

F[i][j]表示架设到了第i根电线杆, 其高度为j时的最小代价

转移 :

F[i][j] = (j-h[i])^2+\min{F[i-1][k]+c\times |k-j|}

复杂度O(NH^2)

优化 :

考虑快速求出那个\min, 把绝对值拆开变成这个样子 :

F[i][j] = (j-h[i])^2+\min{F[i-1][k]+c\times k}-c\times j\;[j\ge k]

F[i][j] = (j-h[i])^2+\min{F[i-1][k]-c\times k}+c\times j\;[j\le k]

对于每一次更新的i括号中的式子只和k有关, 而且可以分别O(H)递推出

g1[k]j\ge k时最小的F[i-1][k]-c\times k

g2[k]j\le k时最小的F[i-1][k]+c\times k

F[i][j] = (j-h[i])^2+\min(g1[j]+c\times j,g2[j]-c\times j)

而递推的式子则为 :

g1[k]=\min(g1[k-1], F[i-1][k]-c\times k)

g2[k] = \min(g2[k+1], F[i+1][k]+c\times k)

特别地, 电线杆不能变矮, 需要注意枚举的边界问题.

代码 :

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int N = 100100;int h[N], f[N][110], g1[110], g2[110];#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}inline int sqr(int x) { return x*x;}int main() { memset(f, 0x3f, sizeof f); int n = rd(), c = rd(), m = 0; for(int i = 1; i <= n; i ++ ) h[i] = rd(), m = max(h[i], m); for(int i=h[1];i <= m; i ++ ) f[1][i] = sqr(i-h[1]); for(int i = 2; i <= n; i ++ ) { memset(g1, 0x3f, sizeof g1); memset(g2, 0x3f, sizeof g2); for(int k = h[i-1]; k <= m; k ++ ) g1[k] = min(g1[k-1], f[i-1][k]-c*k); for(int k = m; k; k -- ) g2[k] = min(g2[k+1], k >= h[i-1] ? f[i-1][k]+c*k : 1<<30); for(int j = h[i]; j <= m; j ++ ) f[i][j] = sqr(j-h[i])+min(g1[j]+c*j, g2[j]-c*j); } int ans = 1<<30; for(int j = 1; j <= m; j ++ ) ans = min(ans, f[n][j]); printf("%d\n", ans);}