合并石子

合并石子

题目描述

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

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

输入格式

第一行为一个正整数 $N$ ( $2\leq N\leq 100$ )；

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

输出格式

一个正整数，即最小得分。

输入样例

7
13
7
8
16
21
4
18

输出样例

239

思路

定义 $dp_{i\ j}$ 为将区间 $[i,\ j]$ 的石子合并成一堆的最小得分。

则可将 $[i,\ j]$ 区间通过一个分割点 $k$ 分为两个部分，问题转化为先合并分割点两端的小区间内的石子，进而将两堆石子合并。

因此，可以通过枚举 $k\ (k \in [i,\ j))$。

状态转移方程：

$dp_{i\ j} = \mathop{min}\limits_{k\in[i,\ j-1]}\{dp_{i\ k} + dp_{k+1\ j} + \sum_{k=i}^{j-1}{v_i}\}$

注意到递推式中存在 $\sum_{k=i}^{j-1}{v_i}$ 项，因此需要预处理前缀和。

同时，需要对 dp数组 初始化。

递推

通过枚举长度 len ，实现求解大状态时，其子状态已经被求得。

通过枚举起点 l， 结合长度 len， 可计算出终点 r，利用状态转移方程求解答案。

void solve()
{
    int n;  cin >> n;
    vector<int> v(n + 1), pre(n + 1, 0);
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
        pre[i] = pre[i - 1] + v[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
    for (int i=0;i<=n;i++)  dp[i][i] = 0;
    for (int len=2;len<=n;len++)
        for (int i=1;i+len-1<=n;i++)
        {
            int l = i, r = i + len - 1;
            for (int j=l;j<r;j++)
                dp[l][r] = min(dp[l][r], dp[l][j] + dp[j + 1][r] + pre[r] - pre[l - 1]);
        }
    cout << dp[1][n];
}

递归

利用带有记忆化的递归，在求解大状态时，若子状态未被计算，则递计算子状态，再归计算大状态，进而求得答案。

void solve()
{
    int n;  cin >> n;
    vector<int> v(n + 1), pre(n + 1, 0);
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
        pre[i] = pre[i - 1] + v[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
    auto work = [&](auto self, int l, int r) -> int
    {
        if (r - l + 1 == 1) return 0;
        if (dp[l][r] != inf)    return dp[l][r];
        
        for (int i=l;i<r;i++)
            dp[l][r] = min(dp[l][r], self(self, l, i) + self(self, i + 1, r) + pre[r] - pre[l - 1]);
        return dp[l][r];
    };

    cout << work(work, 1, n);
}

const int N = 110;
vector<vector<int>> dp(N, vector<int>(N, inf));
vector<int> v(N), pre(N, 0);

int work(int l, int r)
{
    if (r - l + 1 == 1) return 0;
    if (dp[l][r] != inf)    return dp[l][r];
    
    for (int i=l;i<r;i++)
        dp[l][r] = min(dp[l][r], work(l, i) + work(i + 1, r) + pre[r] - pre[l - 1]);
    return dp[l][r];
}

void solve()
{
    int n;  cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
        pre[i] = pre[i - 1] + v[i];
    }
    cout << work(1, n);
}