动态规划 （环形）

在一个圆形操场的四周摆放着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]
    }
}