Stone merging Board [interval DP] (ordinary stone Merging & Ring Stone merging)

[SDOI2008] Stone merging

Common stone merging

Title Description

There are rows of $N$ Rubble . Now we need to combine the stones into a pile in order . It is stipulated that only the adjacent $2$ Make a new pile of stones , And record the new number of stones as the score of the merger .

Try to design an algorithm , Work out what will be $N$ The minimum score for a pile of stones .

Input format

The first line is an integer $N$.

Next $N$ That's ok , The first $i$ Line an integer $a_i$, On behalf of the $i$ The number of stones piled .

Output format

Output the minimum score of merging all stones into a pile .

The board

#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();
}

Ring stones merge

[NOI1995] Stone merging

Title Description

Around a circular playground $N$ Rubble , Now we need to combine the stones into a pile in order , It is stipulated that only the adjacent 2 To merge into a new pile , And count the new pile of stones , Record as the score of the merger .

Try to design an algorithm , Work out what will be $N$ To combine stones into $1$ The minimum and maximum score of the heap .

Input format

The number of data $1$ Lines are positive integers $N$, Express $N$ Rubble .

The first $2$ Yes $N$ It's an integer , The first $i$ It's an integer $a_i$ It means the first one $i$ The number of stones .

Output format

The output, $2$ That's ok , The first $1$ Minimum behavior score , The first $2$ Maximum behavior score .

The board

#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();
}