区间动规经典题——石子合并

题目描述

在一个园形操场的四周摆放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; }