题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式:
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式:
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例#1:
复制
4 4 5 9 4
输出样例#1:
复制
43 54
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #include<cmath> #define Inf 0x3f3f3f3f const int maxn=1e5+5; typedef long long ll; using namespace std; int a[205],g[205][205],sum[205]; int dp[205][205]; int dp2[205][205]; int main() { int n; cin>>n; for(int t=1;t<=n;t++) { scanf("%d",&a[t]); a[n+t]=a[t]; } for(int t=1;t<=2*n;t++) { sum[t]=sum[t-1]+a[t]; } memset(dp,Inf,sizeof(dp)); memset(dp2,0,sizeof(dp2)); for(int t=1;t<=2*n;t++) { for(int j=t;j<=2*n;j++) { g[t][j]=sum[j]-sum[t-1]; } } for(int t=1;t<=2*n;t++) { dp[t][t]=0; } for(int l=1;l<2*n;l++) { for(int j=1;j+l<=2*n;j++) { int r=j+l; for(int k=j;k<r;k++) { dp[j][r]=min(dp[j][r],dp[j][k]+dp[k+1][r]+g[j][k]+g[k+1][r]); dp2[j][r]=max(dp2[j][r],dp2[j][k]+dp2[k+1][r]+g[j][k]+g[k+1][r]); } } } int ans=Inf; int ans1=0; for(int t=1;t<=n;t++) { ans=min(ans,dp[t][t+n-1]); } for(int t=1;t<=n;t++) { ans1=max(ans1,dp2[t][t+n-1]); } cout<<ans<<endl; cout<<ans1<<endl; return 0; }