石子合并板子【区间DP】（普通石子合并 ＆ 环形石子合并）

[SDOI2008] 石子合并

普通石子合并

题目描述

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

试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小得分。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行一个整数 $a_i$，代表第 $i$ 堆石子的石子数。

输出格式

输出将所有石子合并为一堆的最小得分。

板子

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 500;
int n;
int s[N];
int dpm[N][N], dpn[N][N];
void solve()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i],
            s[i] += s[i - 1];

    for (int len = 2; len <= n; len++)
    {
    
        for (int i = 1; i + len - 1 <= n; i++)
        {
    
            int l = i, r = i + len - 1;
             dpm[l][r] = -1;
            dpn[l][r] = 0x3f3f3f3f;
            for (int k = l; k < r; k++)
            {
    
                dpm[l][r] = max(dpm[l][r], dpm[l][k] + dpm[k + 1][r] + s[r] - s[l - 1]);
                dpn[l][r] = min(dpn[l][r], dpn[l][k] + dpn[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }

    cout << dpn[1][n] << '\n'
         << dpm[1][n] << '\n';

}
int main()
{
    
    solve();
}

环形石子合并

[NOI1995] 石子合并

题目描述

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

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

输入格式

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

第 $2$ 行有 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆石子的个数。

输出格式

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

板子

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 500;
int n;
int s[N];
int dpm[N][N], dpn[N][N];
void solve()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i],
            s[i + n] = s[i];

    for (int i = 1; i <= (n << 1); i++)
        s[i] += s[i - 1];

    for (int len = 2; len <= n; len++)
    {
    
        for (int i = 1; i + len - 1 <= (n << 1); i++)
        {
    
            int l = i, r = i + len - 1;
            dpm[l][r] = -1;
            dpn[l][r] = 0x3f3f3f3f;
            for (int k = l; k < r; k++)
            {
    
                dpm[l][r] = max(dpm[l][r], dpm[l][k] + dpm[k + 1][r] + s[r] - s[l - 1]);
                dpn[l][r] = min(dpn[l][r], dpn[l][k] + dpn[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }

    int mx = 0, mn = 0x3f3f3f3f;

    for (int i = 1; i + n - 1 <= (n << 1); i++)
    {
    
        mx = max(mx, dpm[i][i + n - 1]);
        mn = min(mn, dpn[i][i + n - 1]);
    }

    cout << mn << '\n'
         << mx << '\n';
}
int main()
{
    
    solve();
}