重庆市政府渝快办/win10优化工具
题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分
输入输出样例
输入样例：
4
4 5 9 4
输出样例：
43
54
什么是区间动规
区间动态规划问题一般都是考虑，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合 ，求合并后的最优值
题解
由题意可得这些石子是摆放成一个环，环形不好写状态转移方程，那我们就可以把它拆成一条长度为2*n-1 的链，采用区间动规的办法，合并的石子数用前缀和优化一下就好了
状态转移方程：
用f[i][j]表示从第i堆石子到第j堆石子的最大/最小得分，用k(i<=k<=j-1)将区间分成[i,k]和[k+1,j]两个区间
初值:f[i][i]=0
fmax[i][j]=max{fmax[i][j],fmax[i][k]+f[k+1][j]+s[j]-s[i-1]}
fmin[i][j]=min{fmin[i][j],fmin[i][k]+f[k+1][j]+s[j]-s[i-1]}
代码
#include<cstdio>
#include<cstring>
#define MAXN 2*100+5
#define INF 10000000
int fmax[MAXN][MAXN],fmin[MAXN][MAXN],s[MAXN],n,max_ans=-INF,min_ans=INF;
inline int maxx(int x,int y){return x>y?x:y;}
inline int minn(int x,int y){return x<y?x:y;}
void dp()
{
int i,j,k;
for(i=1;i<=2*n-1;++i)
{
for(j=1;j<=2*n-1;++j)
{
fmax[i][j]=-INF;
fmin[i][j]=INF;
}
}
for(i=1;i<=2*n-1;++i)
fmax[i][i]=fmin[i][i]=0;
for(i=2*n-1-1;i>=1;--i)
{
for(j=i+1;j<=2*n-1;++j)
{
for(k=i;k<=j-1;++k)
{
fmax[i][j]=maxx(fmax[i][j],fmax[i][k]+fmax[k+1][j]+s[j]-s[i-1]);
fmin[i][j]=minn(fmin[i][j],fmin[i][k]+fmin[k+1][j]+s[j]-s[i-1]);
}
}
}
}
void get_ans()
{
int i;
for(i=1;i<=n;++i)
{
//寻找长度为n的区间
max_ans=maxx(max_ans,fmax[i][i+n-1]);
min_ans=minn(min_ans,fmin[i][i+n-1]);
}
}
int main()
{
int i,temp;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&temp);
s[i]=s[i+n]=temp;
}
for(i=1;i<=2*n-1;++i)
s[i]+=s[i-1];//前缀和优化
dp();
get_ans();
printf("%d\n%d\n",min_ans,max_ans);
return 0;
}