P 2885[USACO 07 NOV]電話線Telephone Wire-ダイナミックプランニング

いくつかの木の高さを与えて、あなたは1種の操作を行うことができます:ある木をh高くして、h*hに費やします.
操作が完了すると、2本の木の間に高さ差*定値cがかかります.
2種類の費用加算と最小値を求めます.
2 ≤ N ≤ 100,000   1 ≤ height≤ 100
https://www.luogu.org/problemnew/show/P2885
状態:dp[i][j]は前i本の木を表し、i本目の高さはjの最小費用である
初期化:dp[1][i]=(i-a[1])*(i-a[1])(a[1]<=i<=maxn)、maxnが最大の樹高
転移:dp[i][j]=min(dp[i][j],(j-a[i])*(j-a[i])+dp[i-1][k]+abs(j-k)*c)、jはi本目の木の樹高、kはi-1本目の木の樹高
結果:ans=min(ans,dp[n][a[n]~maxn])
この問題解は元の問題の正解ではなく、最適化されていません.最悪の場合O(n*h*h)10億は爆発する.

// luogu-judger-enable-o2
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
using namespace std;
const int N=100001;
const int inf=2147483647;
int n,c,maxn=-1,ans=inf;
int dp[N][201],a[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();c=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        maxn=max(maxn,a[i]);
    }
    memset(dp,127,sizeof(dp));
    for(int i=a[1];i<=maxn;i++){
        dp[1][i]=(i-a[1])*(i-a[1]);
    }
    for(int i=2;i<=n;i++){
        for(int j=a[i];j<=maxn;j++){
            for(int k=a[i-1];k<=maxn;k++){
                dp[i][j]=min(dp[i][j],(j-a[i])*(j-a[i])+dp[i-1][k]+abs(j-k)*c);
            }
        }
    }
    for(int i=a[n];i<=maxn;i++){
        ans=min(ans,dp[n][i]);	
    }
    printf("%d",ans);
    return 0;
}