bzoj 1705: [Usaco2007 Nov]Telephone Wire 架设电话线【dp】

i的初始化写成2了于是成功查错2h……怕不是个傻子

设f[i][j]为第i根高为j，转移是

\[f[i][j]=min(f[i-1][k]+abs(k-j)*c+(j-h[i])^2)(j>=h[i],k>=h[i-1])
\]

时间复杂度是1e5*1e2*1e2，空间复杂度是1e5*1e2，显然都过不了

abs很碍眼，所以考虑分两种情况，化简之后就是

\[f[i][j]=min(f[i-1][k]+k*c)-j*c+(j-h[i])^2(j>=h[i],k>=h[i-1],k>=j)
\]

\[f[i][j]=min(f[i-1][k]-k*c)+j*c+(j-h[i])^2(j>=h[i],k>=h[i-1],k<j)
\]

然后另开数组ad[i][j]表示i根从j到100最大的f[i][j]+jc，mi[i][j]表示i根从a[i]到j最大的f[i][j]-jc，这个可以在求完f[i][]之后直接扫一遍求出，这样时间复杂度就降为了1e5*1e2

然后发现f,ad,mi的i维都没用，所以直接推掉，空间复杂度就变成了1e2（还有1e5的h数组）

就没了

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=100005,inf=1e9;

int n,c,a[N],f[105],ad[105],mi[105],ans=inf;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read(),c=read();

	for(int i=1;i<=n;i++)

		a[i]=read();

	for(int i=a[1];i<=100;i++)

		f[i]=(i-a[1])*(i-a[1]);

	for(int i=1;i<=n;i++)

	{

		if(i!=1)

			for(int j=a[i];j<=100;j++)

				f[j]=min(mi[j]+j*c,ad[max(a[i-1],j+1)]-j*c)+(j-a[i])*(j-a[i]);

		for(int j=0;j<=101;j++)

			ad[j]=mi[j]=inf;

		for(int j=a[i];j<=100;j++)

			mi[j]=min(mi[j-1],f[j]-j*c);

		for(int j=100;j>=a[i];j--)

			ad[j]=min(ad[j+1],f[j]+j*c);

	}

	for(int i=a[n];i<=100;i++)

		ans=min(ans,f[i]);

	printf("%d\n",ans);

	return 0;

}