bzoj1705[Usaco2007Nov]TelephoneWire架设电话线(dp优化)

/*
f[i][j] = min(f[i-1][k]+|j-k|*c+(a[i]-j)*(a[i]-j))
摘出与k无关项得
f[i][j] = min(f[i-1][k]+|j-k|*c) + (a[i]-j)*(a[i]-j)
记P = min(f[i-1][k]+|j-k|*c) , Q = (a[i]-j)*(a[i]-j)
则f[i][j] = P + Q
P = min(A,B),其中
A = min(f[i-1][k]+(j-k)*c) (k<=j)
B = min(f[i-1][k]+(k-j)*c) (k>j)
A = min(f[i-1][k]-k*c) + j*c
B = min(f[i-1][k]+k*c) - j*c
记C[X][i] = min(f[X][k] - k*c)  k∈[1,i]
记D[X][i] = min(f[X][k] + k*c)  k∈[i,n]
则A = C[i-1][j] + j*c
则B = D[i-1][j+1] - j*c
显然C、D在任何时刻只需保存X=i-1一行的值
注意高度只能增高，所以h[i]∈[a[i],100]
利用辅助数组优化后，时间复杂度降为O(N*100)
*/
#include
#include
#include

#define N 100010
#define H 110
#define inf 0x3f3f3f3f

using namespace std;
int n,c,h,P,Q,A,B;
int a[N],C[H],D[H],f[N][H];

int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    h=a[1];
    for(int i=1;i<=n;i++) h=max(h,a[i]);
    h=min(h,100);
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++)
    {
        if(i==1) 
          for(int j=a[i];j<=h;j++)
            f[1][j]=(j-a[1])*(j-a[1]);
        else
        {
            for(int j=a[i];j<=h;j++)
            {
                Q=(j-a[i])*(j-a[i]);
                A=C[j]+j*c;
                B=D[j+1]-j*c;
                P=min(A,B);
                f[i][j]=P+Q;
            }
        }
        C[0]=D[h+1]=inf;
        for(int j=1;j<=h;j++) C[j]=min(C[j-1],f[i][j]-j*c);
        for(int j=h;j>=1;j--) D[j]=min(D[j+1],f[i][j]+j*c);
    }
    int ans=inf;
    for(int i=1;i<=h;i++) ans=min(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
    return 0;
    return 0;
}