Interval DP of Changyou dynamic programming

282. Stone merging

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 310;

int n;       // Number of piles of stones 
int a[N];    // The weight of each stone 
int s[N];    // The prefix and 
int f[N][N]; //f[l][r]  From  [l,r]  The cost of merging into a heap 

void init()
{
    memset(f, 0x3f, sizeof(f)); // Find the minimum value of interval , Initialize to maximum 
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];            // Enter the weight of each stone 
        s[i] = s[i - 1] + a[i]; // Find the prefix and 
        f[i][i] = 0;            // The value of merging a stone itself is 0
    }
}

int main(int argc, char const *argv[])
{
    init();
    for (int len = 2; len <= n; len++)// Enumeration interval length 
    {
        for (int l = 1; l + len - 1 <= n; l++)// Interval starting point 
        {
            int r = l + len - 1;// Interval end point 
            for (int k = l; k < r; k++)// enumeration 
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        } 
    cout << f[1][n] << endl;
    return 0;
}

1068. Ring stones merge

#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>

using namespace std;

const int N = 410;
int n;       // Number of stones 
int a[N];    // The mass of each stone 
int s[N];    // The prefix and 
int f[N][N]; //f[l][r] Express [l,r] The minimum value of interval ranges after merging into a heap 
int g[N][N]; //g[l][r] Express [l,r] The maximum value of interval ranges after merging into a heap 
int INF = 0x3f3f3f3f;

void init()
{
    memset(f, INF, sizeof(f));
    memset(g, -INF, sizeof(g));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        s[i] = s[i - 1] + a[i];
        f[i][i] = 0;
        g[i][i] = 0;
    }
}

int main(int argc, char const *argv[])
{
    for (int len = 2; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= 2 * n; l++)
        {
            int r = l + len - 1;
            for (int k = l; k < r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                g[l][r] = max(g[l][r], f[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
    int maxv = -INF, minv = INF;
    for (int i = 1; i <= n; i++)
    {
        minv = min(minv, f[i][i + n - 1]);
        maxv = max(maxv, f[i][i + n - 1]);
    }
    cout << minv << maxv << endl;
    return 0;
}

320. Energy necklace

#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>

using namespace std;

const int N = 210;
int n;
int a[N];    //a[i] It means the first one i The energy value of each bead 
int f[N][N]; //f[l][r] Means to merge [l,r] The maximum energy obtained by the bead in the range 

int main(int argc, char const *argv[])
{
    // Process input 
    cin >> n; // The number of beads 
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i]; // Copy the interval , The circular linked list is flattened , To be linear 
    }
    for (int len = 3; len <= n + 1; len++)
    {
        for (int l = 1; l + len - 1 <= 2 * n; l++)
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k++)
            {
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res = max(res, f[i][i + n]);
    }
    cout << res << endl;
    return 0;
}