08 四边形不等式优化的环形DP：石子合并

环形DP+四边形不等式优化的区间DP：石子合并

[NOI1995] 石子合并

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4
4 5 9 4

样例输出 #1

43
54

提示

$1\leq N\leq 100$，$0\leq a_i\leq 20$。

考虑的难点主要有两个：

1.区间dp处理环形dp的思路是什么？

2.区间dp的优化方法：四边形不等式；

先解决问题1：

环形dp的处理方法就是将原来的数组扩充两倍，将n+1项写成第1项，将n+2项写成第2项······以此类推。

int n,stone[500],pre[500]={0};
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>stone[i];
        stone[i+n]=stone[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        pre[i]=pre[i-1]+stone[i];
        //cout<<pre[i]<<" ";
    }
    //cout<<endl;

以n=4为例，最后要输出的是

dp[1][4]，dp[2][5]，dp[3][6]，dp[4][7]，dp[5][8]的最小值/最大值，即所有长度为n的区间的最值

int minn=INT_MAX,maxn=0;
    for(int i=1,j=n;j<=2*n;i++,j++)
    {
        minn=min(minn,dpmin[i][j]);
        maxn=max(maxn,dp[i][j]);
    }
    cout<<minn<<endl<<maxn<<endl;

再解决问题2：
先介绍方法：

for (int i = 1; i <= n; ++i)
    m[i][i] = i; // 初始化边界决策点
for (int d = 2; d <= n; ++d)
    for (int l = 1, r = d; r <= n; ++l，++ r)
    {
        dp[l][r] = INF;
        for (int k = m[l][r - 1]; k <= m[l + 1][r];++k) 
        // 利用结论，缩小了枚举范围
            if (dp[l][k] + dp[k + 1][r] + w(l, r) < dp[l][r])
            {
                dp[l][r] = dp[l][k] + dp[k + 1][r] + w(l, r); 
                // 更新dp数组
                m[l][r] = k; 
                // 更新决策点
            }
    }

运用最优决策点的关系，可以实现优化。

然而，我们由上面的文章可以看到，四边形不等式的使用条件其一是w（l，r）满足区间单调性，这个只能数学证明，而且很容易看出来。

其二是，m这个用于标记最佳决策点的数组，在每一行，每一列上都实现单调不下降。本题中，求最大值的时候，m数组不符合这个条件（怎么发现的呢，假设符合条件，然后敲一遍代码，敲完后把m数组打印出来结果如下）

于是就不符合，只能使用简单的区间dp完成。

而求最小值的时候，m数组符合这个条件（运行截图如下），于是就可以使用四边形不等式

完整代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[500][500]={0};
int dpmin[500][500]={0};
int m[500][500]={0};
int m1[500][500]={0};
signed main(void)
{
    int n,stone[500],pre[500]={0};
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>stone[i];
        stone[i+n]=stone[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        pre[i]=pre[i-1]+stone[i];
    }
    //m数组初始化
    for(int i=1;i<=2*n;i++)
    {
        m[i][i]=i;
        m1[i][i]=i;
    }
    for(int e=2;e<=2*n;e++)
    {
        for(int i=1,j=e;j<=2*n;i++,j++)
        {
            dpmin[i][j]=INT_MAX;
            for(int k=i;k<=j-1;k++)
            {
                if(dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]>dp[i][j] && k+1<=j && i<=k)
                {
                    dp[i][j]=dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1];
                    m[i][j]=k;
                }
            }
            for (int k = m1[i][j - 1]; k <= m1[i + 1][j]; k++)
            {
                if (dpmin[i][k] + dpmin[k + 1][j] + pre[j] - pre[i - 1] < dpmin[i][j] && k + 1 <= j && i <= k)
                {
                    dpmin[i][j] = dpmin[i][k] + dpmin[k + 1][j] + pre[j] - pre[i - 1];
                    m1[i][j] = k;
                }
            }
        }
    }
    int minn=INT_MAX,maxn=0;
    for(int i=1,j=n;j<=2*n;i++,j++)
    {
        minn=min(minn,dpmin[i][j]);
        maxn=max(maxn,dp[i][j]);
    }
    cout<<minn<<endl<<maxn<<endl;
    return 0;
}