一本通-1274：【例9.18】合并石子（直线排列，小数据）

【题目描述】 在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

计算出将Ｎ堆石子合并成一堆的最小得分。

【输入】 第一行为一个正整数N (2≤Ｎ≤100)；

以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。

【输出】 一个正整数，即最小得分。

【输入样例】 7 13 7 8 16 21 4 18

【输出样例】 269

---

解法一：朴素动态规划，时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int INF = 0xffffff;

int n;
vector<int> seq(105), preSum(105);
vector<vector<int> > d(105, vector<int>(105, INF)), p(105, vector<int>(105, -1));

int solve()
{
    for (int i = 1; i <= n; ++i) {
        d[i][i] = 0;
        preSum[i] = preSum[i - 1] + seq[i - 1];
    }

    for (int len = 2; len <= n; ++len) { //根据长度划分阶段
        for (int i = 1; i <= n - len + 1; ++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]);
            d[i][j] += preSum[j] - preSum[i - 1];
        }
    }

    return d[1][n];
}

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];

    cout << solve() << endl;

    return 0;
}

解法二：四边形不等式优化，时间复杂度$O(n^2)$

#include <bits/stdc++.h>

using namespace std;

const int INF = 0xffffff;

int n;
vector<int> seq(105), preSum(105);
vector<vector<int> > d(105, vector<int>(105, INF)), p(105, vector<int>(105, -1));

int solve()
{
    for (int i = 1; i <= n; ++i) { 
        d[i][i] = 0; 
        p[i][i] = i; 
        preSum[i] = preSum[i - 1] + seq[i - 1];
    }

    for (int len = 1; len < n; ++len) { //枚举区间长度
        for (int i = 1; i + len <= n; ++i) { //区间左端点
            int j = i + len; //区间右端点
            for (int k = p[i][j - 1]; k <= p[i + 1][j]; ++k) {
                if (d[i][k] + d[k + 1][j] + preSum[j] - preSum[i - 1] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k + 1][j] + preSum[j] - preSum[i - 1];
                    p[i][j] = k;
                }
            }
        }
    }

    return d[1][n];
}

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];

    cout << solve() << endl;

    return 0;
}