题目
题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入格式
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式
输出共2行,第1行为最小得分,第2行为最大得分.
样例输入
|
1 2 3 4 |
4 4 5 9 4 |
样例输出
|
1 2 3 4 |
43 54 |
题解
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstdio> #include<cstring> #define MAXN 402 using namespace std; int fmin[MAXN][MAXN]; int sum[MAXN]; int fmax[MAXN][MAXN]; int n; int main(){ memset(fmin,0x3f,sizeof(fmin)); memset(fmax,0,sizeof(fmax)); scanf("%d",&n); for(int i=1;i<=n;i++){ int a; scanf("%d",&a); fmin[i][i]=0; fmin[i+n][i+n]=0; sum[i]=sum[i-1]+a; } for(int i=1;i<=n;i++){ sum[i+n]=sum[n]+sum[i]; } for(int len=2;len<=n;len++){ for(int i=1;i<=n+n-len+1;i++){ int j=i+len-1; for(int k=i;k<j;k++){ fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]); fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]); } } } int minn=1<<30; int maxx=0; for(int i=1;i<=n;i++){ minn=min(minn,fmin[i][i+n-1]); maxx=max(maxx,fmax[i][i+n-1]); } printf("%d\n%d",minn,maxx); return 0; } |