洛谷-P1880 [NOI1995]石子合并（环形区间DP）

题目描述

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

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

输入格式

数据的第 11 行是正整数 N*N*，表示有 N*N* 堆石子。

第 22 行有 N*N* 个整数，第 i*i* 个整数 a_i*a**i* 表示第 i*i* 堆石子的个数。

输出格式

输出共 22 行，第 11 行为最小得分，第 22 行为最大得分。

输入输出样例

输入 #1

4
4 5 9 4

输出 #1

43
54

说明/提示

1\leq N\leq 1001≤N≤100，0\leq a_i\leq 200≤a**i≤20。

---

#include <bits/stdc++.h>

using namespace std;

const int INF = 0xffffff;

vector<int> seq(205), preSum(205);
vector<vector<int>> d(205, vector<int>(205, INF)), f(205, vector<int>(205, -INF));
int n;


void stoneMerge()
{
    for (int i = 1; i <= 2 * n; ++i) {
        d[i][i] = 0;
        f[i][i] = 0;
        preSum[i] = preSum[i - 1] + seq[i - 1];
    }

    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
                d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j] + preSum[j] - preSum[i - 1]);
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + preSum[j] - preSum[i - 1]);
            }
        }
    }

    int minVal = INT_MAX, maxVal = INT_MIN;
    for (int i = 1; i <= n; ++i) {
        minVal = min(minVal, d[i][i + n - 1]);
        maxVal = max(maxVal, f[i][i + n - 1]);
    }

    cout << minVal << endl << maxVal << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i];
        seq[i + n] = seq[i];
    }

    stoneMerge();

    return 0;
}

石子合并的环形处理，采用扩展域，然后相当于对长度为n的连续序列做线性情况的石子合并。时间复杂度$O(n^3)$。