设dp[i][j]表示第i个数变为j的最小代价。

则dp[i][j]=min{dp[i-1][k]+c*abs(j-k)+(j-h[i])^2}（k是第i-1位上的数，j是当前位上的数）

100000*100*100。。哗~萎掉了。。

把abs(j-k)拆开试试？

j>k时：dp[i][j]=min{dp[i-1][k]+c*j-c*k+(j-h[i])^2}=min{dp[i-1][k]-c*k}+c*j+(j-h[i])^2

j<k时：dp[i][j]=min{dp[i-1][k]+c*k-c*j+(j-h[i])^2}=min{dp[i-1][k]+c*k}-c*j+(j-h[i])^2

那么我们只要在每次转移的时候记录f数组表示min{dp[i-1][k]-c*k}，g数组表示min{dp[i-1][k]+c*k}。这样转移的时候就是O(10w*100)了~

至于空间的话，第一维好像一点用都没有。那就不要了！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define abs(x) (((x)<0)?(-(x)):(x))
#define sqr(x) ((x)*(x))
int dp[105],f[105],g[105],h[100005],n,c;
const int inf=1061109567;
char buf[2000000],*p=buf;
inline int getint(){
    int r=0;while(*p<48||*p>57)p++;while(*p>47&&*p<58)r=r*10+*p++-'0';return r;
}int main(){
    fread(buf,1,2000000,stdin); n=getint(),c=getint();
    for(int i=1;i<=n;i++) h[i]=getint();
    memset(dp,63,sizeof(dp));
    for(int i=h[1];i<=100;i++) dp[i]=sqr(i-h[1]);
    for(int i=2;i<=n;i++){
        f[101]=inf; for(int j=100;j>=1;j--) f[j]=min(dp[j]+j*c,f[j+1]);
        g[0]=inf;   for(int j=1;j<=100;j++) g[j]=min(dp[j]-j*c,g[j-1]);
        memset(dp,63,sizeof(dp));
        for(int j=h[i];j<=100;j++) dp[j]=sqr(j-h[i])+min(g[j]+j*c,f[j]-j*c);
    }int An=inf;
    for(int i=1;i<=100;i++) An=min(An,dp[i]);
    printf("%d\n",An);  return 0;
}

• 相关文章