动态规划 （环形）

在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

输入格式:

n表示n堆石子，下一行n个数，表示每堆石子的个数。可能有多组测试数据。

输出格式:

分别输出最小得分和最大得分，空格隔开。每组一行。

输入样例:

在这里给出一组输入。例如：

4
4  4  5  9

输出样例:

在这里给出相应的输出。例如：

43 54

 注：连着找最值 不能 直接找最值合并 例1 3 4 2 5

二维数组几乎全部用到了 不是三角形状 行代表起点开始的位置 列代表从起点开始向后的距离

#include <stdio.h>int main()
{int n;while(scanf("%d",&n)!=EOF){int a[n+1],max[n+1][n+1],min[n+1][n+1];for (int i=0;i<n+1;i++)//二维数组全部初始化为0{for (int j=0;j<n+1;j++){min[i][j]=0;max[i][j]=0;}}for (int i=1;i<n+1;i++)//输入scanf("%d",&a[i]);for (int len=2;len<=n;len++)//分割长度，从2开始到n结束{for (int begin=1;begin <=n;begin++)//起点{int end = begin+len-1;        //终点if (end>n)                    //大于才取模 因为从1开始 需要分情况 从0开始不需要end=end%n;for (int k=1;k<len;k++)        //分割的长度 从1开始 {int sum=0,loc=begin;        //记录合并后需要新加的数for (int ii=0;ii<len;ii++) {sum+=a[loc++];if (loc>n)loc=(loc)%n;}loc=k+begin;if (loc>n)loc=loc%n;//二维数组几乎全部用到了 不是三角形状 行代表起点开始的位置 列代表从起点开始向后的距离if(!min[begin][len] || min[begin][len] > min[begin][k] + min[loc][len-k] + sum )min[begin][len] = min[begin][k] + min[loc][len-k] + sum;if (!max[begin][len] || max[begin][len] < max[begin][k] + max[loc][len-k] + sum )max[begin][len] = max[begin][k] + max[loc][len-k] + sum;}}}int Min=99999,Max=0;for (int i=1;i<=n;i++)        //列代表从起点开始向后的距离 所以需要遍历所有起点且距离为n的位置{if (Min > min[i][n])Min = min[i][n];if (Max < max[i][n])Max = max[i][n];}printf("%d %d\n",Min ,Max);//[1][n]}
}