DP(4)--区间DP

将n(1≤n≤200)堆石子绕圆形操场摆放，现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 
(1)选择一种合并石子的方案，使得做n-1次合并，得分的总和最小。 
(2)选择一种合并石子的方案，使得做n-1次合并，得分的总和最大
输入
4
4 5 9 4
输出
43
54

线性结构是N个数据元素以有序的方式排列。访问线性结构一般采用由前至后的遍历方法。
线性动态规划就是在线性数据的基础上，通过某种递推方式（状态转移方程）得到最终结构的一种规划算法。
sum[i]: 从第1堆到第i堆石子数总和
fmax[i][j]: 从第i堆石子合并到第j堆石子的最大得分
fmin[i][j]: 从第i堆石子合并到第j堆石子的最小得分

初始化： fmax[i][i] = 0, fmin[i][i]= INF
状态方程：
fmax[i][j] = max{fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]} i <= k < j
fmin[i][j] = min{fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]} i <= k < j

由于题中围成一个环，我们将这条链再延长一倍，变成2*n堆，地中第i堆与第n+i堆相同，
动态规划求解后，答案为f(1,n), f(2,n+1), ... , f(n-1,2*n-2)中的最优解

状态转移
要计算f(i,j)的值时需知道所有f(i,k)和f(k+1,j)的值，
以len=j-i+1作为DP 的区间长度，从小到大枚举len，
然后枚举i的值，根据len和i用公式计算出j的值，然后枚举k，时间复杂度为O(n^3)

/*  https://loj.ac/problem/10147  */
#include <iostream>
using namespace std;

const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];

int main()
{
    int i, j, k, n, len;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n+i] = arr[i]; 
    }
    for (i = 1; i <=(n<<1); ++i)
        sum[i] = sum[i-1] + arr[i];

    for (len = 2; len <= n; ++len)
        for (i = 1; i <= (n<<1)-len+1; ++i)
        {
            j = i + len - 1;
            // 初始化
            fmax[i][j] = 0;
            fmin[i][j] = INF;
            for (k = i; k < j; ++k)
            {
                fmax[i][j] = max(fmax[i][j], fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1]);
                fmin[i][j] = min(fmin[i][j], fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1]);
            }
        }

    int ansmax = 0, ansmin = INF;
    for (i = 1; i < n; ++i)
    {
        ansmax = max(ansmax, fmax[i][i+n-1]);
        ansmin = min(ansmin, fmin[i][i+n-1]);
    }

    cout << ansmin << endl << ansmax << endl;

    return 0;
}

四边形不等式优化请参考

https://oi-wiki.org/dp/opt/quadrangle/

https://www.cnblogs.com/a1b3c7d9/p/10984353.html

dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]} (i≤k<j)
把dp[i][k]+dp[k+1][j]取得最值的那个k, 称为dp[i][j]的最优决策点。

 

 

#include <iostream>
using namespace std;
const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];
int ma[2*MAXN][2*MAXN]; //ma[i][j]： 从第i堆石子合并到第j堆石子的最大得分时的最优决策点
int mi[2*MAXN][2*MAXN]; //mi[i][j]： 从第i堆石子合并到第j堆石子的最小得分时的最优决策点

int main()
{
    int i, j, k, n, len, t;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n+i] = arr[i];
    }
    for (i = 1; i <=(n<<1); ++i)
    {
        sum[i] = sum[i-1] + arr[i];
        ma[i][i] = i;
        mi[i][i] = i;
    }

    for (len = 2; len <= n; ++len)
        for (i = 1; i <= (n<<1)-len+1; ++i)
        {
            j = i + len - 1;
            // 初始化
            fmax[i][j] = 0;
            fmin[i][j] = INF;
            // 四边形不等式优化
            for (k = ma[i][j-1]; k <= ma[i+1][j] && k < j; ++k)
            {
                t = fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1];
                if (fmax[i][j] < t)
                {
                    fmax[i][j] = t;
                    ma[i][j] = k;
                }
            }

            for (k = mi[i][j-1]; k <= mi[i+1][j] && k < j; ++k)
            {
                t = fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1];
                if (fmin[i][j] > t)
                {
                    fmin[i][j] = t;
                    mi[i][j] = k;
                }
            }
        }

    int ansmax = 0, ansmin = INF;
    for (i = 1; i < n; ++i)
    {
        ansmax = max(ansmax, fmax[i][i+n-1]);
        ansmin = min(ansmin, fmin[i][i+n-1]);
    }

    cout << ansmin << endl << ansmax << endl;

    return 0;
}