石子合并问题--直线版（矩阵相乘）

一条直线上摆放着一行共 n 堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将 n 堆石子合并成一堆的最小得分和将 n 堆石子合并成一堆的最大得分。 Input

输入有多组测试数据。

每组第一行为n(n<=100)，表示有n堆石子。

二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）

Output 每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。 Sample Input

3

1 2 3

Sample Output 9 11 题意：两两堆数相加求最大分堆与最小分堆 题解：并相邻的两堆石子相当于矩阵连乘问题 #include<stdio.h> #include<string.h> #define INF 0x3f3f3f3f #define max(a,b)a>b?a:b #define min(a,b)a<b?a:b int a[105]; int dpmax[105][105]; int dpmin[105][105]; int main(){ int n; while(~scanf("%d",&n)){ a[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]+=a[i-1]; } memset(dpmin,0,sizeof(dpmin)); memset(dpmax,0,sizeof(dpmax)); for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++){ int j=r+i-1; dpmin[i][j]=INF; dpmax[i][j]=-INF; //sum[j]-sum[i-1]表示该区间的石子数 for(int k=i;k<j;k++){ dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+a[j]-a[i-1]); dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+a[j]-a[i-1]); } } printf("%d %d\n",dpmin[1][n],dpmax[1][n]); } }