HRBUST - 1819 石子合并问题--圆形版 （区间dp）

在圆形操场上摆放着一行共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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int N = 205;

int a[N], pre[N];
int dp[N][N][2];    //dp[i][j][0] 代表从i到j的最小值，dp[i][j][1]代表最大值

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        pre[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            pre[i] = pre[i - 1] + a[i];
        }
        for(int i = n + 1; i <= 2 * n; ++i)
        {
            pre[i] = pre[i - 1] + a[i - n];
        }
        for(int i = 2; i <= 2 * n; ++i)    //长度
        {
            for(int l = 1; l <= 2 * n - i + 1; ++l)    //起点
            {
                int r = l + i - 1;
                dp[l][r][0] = dp[l + 1][r][0];
                dp[l][r][1] = dp[l + 1][r][1];
                for(int j = l + 1; j < r; ++j)
                {
                    dp[l][r][0] = min(dp[l][r][0], dp[l][j][0] + dp[j + 1][r][0]);
                    dp[l][r][1] = max(dp[l][r][1], dp[l][j][1] + dp[j + 1][r][1]);
                }
                dp[l][r][0] += pre[r] - pre[l - 1];
                dp[l][r][1] += pre[r] - pre[l - 1];
            }
        }
        int ans1 = inf;
        int ans2 = -inf;
        for(int i = 1; i <= n; ++i)
        {
            ans1 = min(ans1, dp[i][i + n - 1][0]);
            ans2 = max(ans2, dp[i][i + n - 1][1]);
        }
        cout<<ans1<<' '<<ans2<<'\n';
    }
    return 0;
}