PKU 3612 Telephone Wire

クリスマスですね。

日本語の解説記事がなかったので。
まずは普通に
dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値
(不可能なときはINF)として漸化式をたててみると
dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0<=k<=100} + (j-h[i])^2
となりますが、コレを愚直に実装するとO(N*(H_MAX)^2)で間に合いません。
そこで
dp[i][j] = min(min{dp[i-1][k]+k*C-j*C|j<=k<=100},min{dp[i-1][k]-k*C+j*C|0<=k<=j})+(j-h[i])^2
として(絶対値で場合分けしただけです)
a[i][j] = min{dp[i][k]+k*C|j<=k<=100}
b[i][j] = min{dp[i][k]+k*C|0<=k<=j}
とおくと、dp[i][j]=min(a[i-1][j]-j*C,b[i-1][j]+j*C)+(j-h[i])^2と書けます。
a[i],b[i]はdp[i]の計算が終わった後にO(H_MAX)で求められるので
全体としてO(N(H_MAX))で計算できます

#define sq(X) ((X)*(X))
int dp[2][105],a[2][105],b[2][105];
int h[100100],N,C;
int main()
{
	scanf("%d %d",&N,&C);
	for(int i=0;i<N;i++)scanf("%d",&h[i]);
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=100;j++)
		{
			dp[i%2][j]=INF;
			a[i%2][j]=INF;
			b[i%2][j]=INF;
		}
		for(int j=h[i];j<=100;j++)
		{
			if(i==0)dp[i%2][j]=sq(j-h[i]);
			else dp[i%2][j]=min(a[(i-1)%2][j]-j*C,b[(i-1)%2][j]+j*C)+sq(j-h[i]);
		}
		for(int j=100;j>=0;j--)
		{
			if(j==100)a[i%2][j]=dp[i%2][j]+j*C;
			else a[i%2][j]=min(a[i%2][j+1],dp[i%2][j]+j*C);
		}
		for(int j=0;j<=100;j++)
		{
			if(j==0)b[i%2][j]=dp[i%2][j]-j*C;
			else b[i%2][j]=min(b[i%2][j-1],dp[i%2][j]-j*C);
		}
	}
	int ans = INF;
	for(int i=0;i<=100;i++)ans = min(ans,dp[(N-1)%2][i]);
	printf("%d\n",ans);
	return 0;
}