石子合并2

【题目描述】

在一个圆形操场的四周摆放N堆石子(N ≤ 100)，现要将石子有次序地合并成一堆，规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。

现询问将N堆石子合并为一堆，能够得到的最大得分和最小得分是多少。

【输入描述】

输入包含多组数据。

第一行输入一个数N，表示石子堆的数目；

接下来N行，每行输入一个数，表示每堆石子的数目；

当N=0时，输入结束。

【输出描述】

对于每组数据，输出一行，包含两个数，表示答案。

【输入样例】

6

30 35 15 5 10 20

3

1 2 3333

6

3 4 5 6 7 8

0

【输出样例】

275 475

3339 6671

84 125

源代码：

#include<cstdio>
#include<algorithm>
#define INF 1000000000
using namespace std;
int n,Max=0,Min=INF,i[101],f1[201][201],f2[201][201],sum[201]; //注意数据范围，f1[i][j]表示[i,j]合并的最小代价，f2[i][j]表示最大代价。
void DP()
{
    for (int a=2;a<=n;a++)
      for (int b=1;b<=(n<<1)-a+1;b++)
      {
          int t=b+a-1;
          f1[b][t]=INF;
          for (int c=b;c<t;c++)
          {
              f1[b][t]=min(f1[b][t],f1[b][c]+f1[c+1][t]+sum[t]-sum[b-1]);
              f2[b][t]=max(f2[b][t],f2[b][c]+f2[c+1][t]+sum[t]-sum[b-1]);
　　　　　　}

      }
} 
int main()
{
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
    {
        scanf("%d",&i[a]);
        i[a+n]=i[a];
    }
    for (int a=1;a<=(n<<1);a++) //前缀和处理。
      sum[a]=sum[a-1]+i[a];
    DP();
    for (int a=1;a<=n;a++)
    { 
        Min=min(Min,f1[a][a+n-1]);
        Max=max(Max,f2[a][a+n-1]);
    }
    printf("%d
%d",Min,Max);
    return 0;
}

/*
    总体思想还是和链状合并类似的。
    采取“断环为链”的思想，将DP长度扩至[1,2*n]，便能囊括所有情况。
*/