题目传送门(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);}