题目描述

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

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入格式

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例

输入 #1复制

4
4 5 9 4

输出 #1复制

43
54

题解

#include <bits/stdc++.h>
using namespace std;

const int maxn = 201;
const int inf = 1e9;
int n, sum, Min, Max, a[maxn], presum[maxn];
int dpmax[maxn][maxn], dpmin[maxn][maxn];

int getMin(int i, int j)
{
    if (i == j) return 0;
    if (dpmin[i][j]) return dpmin[i][j];
    int res = inf;
    for (int k = i; k < j; k++)
        res = min(res, getMin(i, k) + getMin(k + 1, j) + presum[j] - presum[i - 1]);
    return dpmin[i][j] = res;
}

int getMax(int i, int j)
{
    if (i == j) return 0;
    if (dpmax[i][j]) return dpmax[i][j];
    int res = 0;
    for (int k = i; k < j; k++)
        res = max(res, getMax(i, k) + getMax(k + 1, j) + presum[j] - presum[i - 1]);
    return dpmax[i][j] = res;
}

int main()
{
    Min = inf;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        a[i + n] = a[i];
        presum[i] = sum += a[i];
    }
    for (int i = 1; i <= n; i++)
        presum[i + n] = presum[i] + presum[n];
    for (int i = 1; i <= n; i++)
    {
        Min = min(Min, getMin(i, i + n - 1));
        Max = max(Max, getMax(i, i + n - 1));
    }
    printf("%d\n%d\n", Min, Max);
    return 0;
}