本文主要是介绍山河令[区间DP]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分析
(https://blog.csdn.net/dreaming__ldx/article/details/83447762)
#include<bits/stdc++.h>
#define N 55
#define inf 0x3fffffff
using namespace std;
int x[N],w[N];
int n,a,b;
int g[N][N][N][N],f[N][N];
int read(){int cnt=0; char ch=0;while(!isdigit(ch)) ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}
int main(){n=read(),a=read(),b=read();for(int i=1;i<=n;i++) x[i]=w[i]=read();sort(x+1,x+n+1);int siz=unique(x+1,x+n+1)-(x+1);for(int i=1;i<=n;i++) w[i]=lower_bound(x+1,x+siz+1,w[i])-x;for(int i=1;i<=n;i++) f[i][i]=a;for(int len=2;len<=n;len++){for(int l=1,r=len;r<=n;l++,r++){/*----------------------------初始化----------------------------*/for(int i=l;i<=r;i++)for(int j=siz;j;j--)for(int k=siz;k>=j;k--)g[l][i][j][k]=inf;g[l][l][w[l]][w[l]]=0;/*----------------------------更新G------------------------------*/for(int i=l;i<r;i++)for(int j=siz;j;j--)for(int k=siz;k>=j;k--){if(g[l][i][j][k]==inf) continue;int &tmp=g[l][i+1][min(j,w[i+1])][max(k,w[i+1])];tmp=min(tmp,g[l][i][j][k]);for(int t=i+1;t<=r;t++) g[l][t][j][k]=min(g[l][t][j][k],g[l][i][j][k]+f[i+1][t]); }/*---------------------------更新F------------------------------*/f[l][r]=inf;for(int i=siz;i;i--)for(int j=siz;j>=i;j--)f[l][r]=min(f[l][r],g[l][r][i][j]+a+b*(x[j]-x[i])*(x[j]-x[i])); }}printf("%d\n",f[1][n]); return 0;
}
这篇关于山河令[区间DP]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
