Description
期末考试结束了，班主任L老师要将成绩单分发到每位同学手中。L老师共有n份成绩单，按照编号从1到n的顺序叠
放在桌子上，其中编号为i的成绩单分数为w_i。成绩单是按照批次发放的。发放成绩单时，L老师会从当前的一叠
成绩单中抽取连续的一段，让这些同学来领取自己的成绩单。当这批同学领取完毕后，L老师再从剩余的成绩单中
抽取连续的一段，供下一批同学领取。经过若干批次的领取后，成绩单将被全部发放到同学手中。然而，分发成绩
单是一件令人头痛的事情，一方面要照顾同学们的心理情绪，不能让分数相差太远的同学在同一批领取成绩单；另
一方面要考虑时间成本，尽量减少领取成绩单的批次数。对于一个分发成绩单的方案，我们定义其代价为：
其中，k是方案中分发成绩单的批次数，对于第i批分发的成绩单，〖max〗_i是最高分数，〖min〗_i是最低分数。
a,b是给定的评估参数。现在，请你帮助L老师找到代价最小的分发成绩单的方案，并将这个最小的代价告诉L老师
。当然，分发成绩单的批次数k是由你决定的。
Input
第一行包含一个正整数n，表示成绩单的数量。
第二行包含两个非负整数a,b，表示给定的评估参数。
第三行包含n个正整数w_i，表示第i张成绩单上的分数。
Output
仅一个正整数，表示最小的代价是多少。
Sample Input
10
3 1
7 10 9 10 6 7 10 7 1 2
Sample Output
15
【样例数据说明】
第1批：第2至4份成绩单，落差值为1，剩余成绩单为76710712；
第2批：第4份成绩单，落差值为0，剩余成绩单为767712；
第3批：第1至4份成绩单，落差值为1，剩余成绩单为12；
第4批：剩余的2份成绩单，落差值为1。
总代价为4×3+(1^2+0^2+1^2+1^2)×1=15。
HINT
n<=50, a<=100, b<=10, w_i<=1000
思路:
注意是从中间抽，否则就太简单了。
每次抽肯定是一个子序列，且中间的空都是被抽空了。
设g[l][r]表示区间[l,r]被抽空的最小代价,f[l][r][i][j]表示区间[l,r]最后一抽最小值为i,
最大值为j,且强制要选a[l],a[r]的最小代价,
f[l][r][i][j]+g[r+1][R-1]→f[l][R][min(i,a[R])][max(j,a[R])])
f[l][r][i][j]+g[r+1][R]+A+B*(j-i)^2→g[l][R]
代码+双倍经验
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<iomanip> #include<cstdlib> #include<queue> #include<map> #include<set> #include<stack> #include<vector> #define ll long long using namespace std; inline int read() { int s=0,w=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} while(isdigit(ch)) s=s*10+ch-'0',ch=getchar(); return s*w; } int n,mx,A,B,a[55],b[55],f[55][55][55][55],g[55][55]; void checkmin(int &x,int y) { x=x<y?x:y; } int main() { n=read(),A=read(),B=read(); for(int i=1;i<=n;i++) a[i]=b[i]=read(); sort(b+1,b+n+1),mx=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+mx+1,a[i])-b; memset(f,0x3f3f3f3f,sizeof f),memset(g,0x3f3f3f3f,sizeof g); for(int i=1;i<=n;i++) f[i][i][a[i]][a[i]]=0,g[i][i]=A,g[i][i-1]=0; g[n+1][n]=0; for(int l=n;l;l--) for(int r=l;r<=n;r++) for(int i=1;i<=mx;i++) for(int j=i;j<=mx;j++) if(f[l][r][i][j]!=0x3f3f3f3f) { for(int nr=r+1;nr<=n;nr++) checkmin(f[l][nr][min(i,a[nr])][max(j,a[nr])],f[l][r][i][j]+g[r+1][nr-1]); for(int nr=r;nr<=n;nr++) g[l][nr]=min(g[l][nr],f[l][r][i][j]+g[r+1][nr]+A+B*(b[j]-b[i])*(b[j]-b[i])); } printf("%d",g[1][n]); return 0; }