退役了退役了，刷点水题准备面试

题目描述

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

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

输入格式

数据的第 1 行是正整数 N，表示有 N 堆石子。
第 2 行有 N 个整数，第 i 个整数 ai​ 表示第 i 堆石子的个数。

输出格式

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

输入样例

4
4 5 9 4

输出样例

43
54

Hint

1 <= N <= 100，0 <= Ai <= 20

题解

把环复制一遍变成链做 dp 就行了

F(i, j) 表示合并 [i, j] 的最大得分
F(i, j) = max { F(i, k) + F(k+1, j) + Sum(i, j), i <= k < j }
最小得分同理

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;

const int MAXN = 205;

int N;
long long A[MAXN];
long long F[MAXN][MAXN];
long long G[MAXN][MAXN];
long long S[MAXN];

int main() {
    memset (G, 0x0f, sizeof(G));
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%lld", A + i), A[i+N] = A[i], G[i][i] = G[i+N][i+N] = 0;
    for (int i = 1; i <= N * 2; i++)
        S[i] = S[i - 1] + A[i];
    for (int l = 2; l <= N; l++)
        for (int i = 1; i+l-1 <= 2*N; i++)
            for (int j = 1; j < l; j++)  {
                F[i][i+l-1] = max(F[i][i+l-1], F[i][i+j-1] + F[i+j][i+l-1] + S[i+l-1] - S[i-1]);
                G[i][i+l-1] = min(G[i][i+l-1], G[i][i+j-1] + G[i+j][i+l-1] + S[i+l-1] - S[i-1]);
            }
    long long ansMn = INT_MAX;
    long long ansMx = INT_MIN;
    for (int i=1; i<=N; i++) {
        ansMx = max (ansMx, F[i][i+N-1]);
        ansMn = min (ansMn, G[i][i+N-1]);
    }
    printf("%lld\n%lld", ansMn, ansMx);
    return 0;
}