题目描述
在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的 2 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。
输入格式
数据的第 1 行是正整数 N,表示有 N 堆石子。
第 2 行有 N 个整数,第 i 个整数 ai 表示第 i 堆石子的个数。
输出格式
输出共 2 行,第 1 行为最小得分,第 2 行为最大得分。
输入输出样例
输入 #1
4
4 5 9 4
输出 #1
43
54
说明/提示
1≤N≤100,0≤ai≤20。
分析
由于石子摆在圆形操场的四周,因此 n 堆石子会摆放成一个环,于是不妨将 n 堆石子复制一份,使得 ai=ai+n。
定义 dpmin[i][j] 为合并区间 [i,j] 内石子获得的最小得分,有状态转移方程 dpmin[i][j]=i≤k<jmin(dpmin[i][k]+dpmin[k+1][j]+count(i,j))。同理,定义 dpmax[i][j] 为合并区间 [i,j] 内石子获得的最大得分,有状态转移方程 dpmax[i][j]=i≤k<jmax(dpmax[i][k]+dpmax[k+1][j]+count(i,j))。所求即为 1≤i≤n−1mindpmin[i][i+n] 和 1≤i≤n−1maxdpmax[i][i+n]。
代码
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<algorithm> #include<cstring> #include<iostream> #include<cstdio> #define N 302 using namespace std; int dp_min[N][N]; int dp_max[N][N]; int n; int sum[N]; int a[N]; int main() { memset(dp_min,0x3f,sizeof(dp_min)); memset(dp_max,0,sizeof(dp_max)); int i,j,k; cin>>n; for(i=1;i<=n;i++) scanf("%d",a+i); for(i=n+1;i<=2*n;i++) a[i]=a[i-n]; for(i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; for(j=1;j<=2*n;j++) { for(i=j;i>=1;i--) { if(i==j) dp_min[i][j]=dp_max[i][j]=0; for(k=i;k<j;k++) { dp_min[i][j]=min(dp_min[i][k]+dp_min[k+1][j]+sum[j]-sum[i-1],dp_min[i][j]); dp_max[i][j]=max(dp_max[i][k]+dp_max[k+1][j]+sum[j]-sum[i-1],dp_max[i][j]); } } } int ans_min=0x3f3f3f3f,ans_max=-1; for(i=1;i<=n-1;i++) { ans_min=min(ans_min,dp_min[i][i+n-1]); ans_max=max(ans_max,dp_max[i][i+n-1]); } cout<<ans_min<<endl<<ans_max<<endl; return 0; }
|