四边形不等式优化之石子归并与矩阵链乘之区别

ACM模版

很久以前做过一个环形石子归并的题目，因为数据较大、复杂度较高， O(n3) O ( n 3 ) ，所以 TLE T L E 了，需要用到四边形不等式优化一下，几乎降低复杂度到 O(n2) O ( n 2 ) ，才能 AC A C 。

我们先来看一下这个题目：

描述：

代码：

#include <iostream>

using namespace std;

const int MAXN = 2020;
const int INF = 0x3f3f3f3f;

int A[MAXN];
int S[MAXN][MAXN];
int W[MAXN][MAXN];
int dp[MAXN][MAXN] = {
  0};

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
        A[i + N] = A[i];
    }

    int N_ = 2 * N;
    for (int i = 1; i < N_; i++)
    {
        for (int j = i; j <= i + N; j++)
        {
            W[i][j] = W[i][j - 1] + A[j];
        }
        S[i][i] = i;
    }

    for (int len = 2; len <= N; len++)
    {
        for (int i = 1; i + len - 1 <= N_; i++)
        {
            int j = i + len - 1;
            dp[i][j] = INF;
            for (int k = S[i][j - 1]; k <= S[i + 1][j]; k++)
            {
                int temp = dp[i][k] + dp[k + 1][j] + W[i][j];
                if (temp < dp[i][j])
                {
                    dp[i][j] = temp;
                    S[i][j] = k;
                }
            }
        }
    }

    int res = INF;
    for (int i = 1; i <= N; i++)
    {
        res = res < dp[i][i + N - 1] ? res : dp[i][i + N - 1];
    }
    cout << res << endl;

    return 0;
}

在这个代码中，四边形不等式优化用到了 S[][] S [ ] [ ] 数组，利用它来大大缩小了 k k 的取值范围，主要体现在第 48 $48$ 行代码，那么四边形不等式优化的结论到底是什么呢？

设 d 为区间 [i,j] [ i , j ] 最优解（一般是代价、权值），即 d=dp[i][j] d = d p [ i ] [ j ] ，那么 dp[i][j−1]<=d<=dp[i+1][j] d p [ i ] [ j − 1 ] <= d <= d p [ i + 1 ] [ j ] 。

具体原理是什么百度你会找到很多……

根据上述结论，我们不难看出来这个其实和动态规划是息息相关的，四边形不等式优化在动态规划中是一个很重要的优化手段。

不过问题也来了，我们题目中 S[][] S [ ] [ ] 中保存的明显不是代价或者权值，因为他控制的是 k k 的范围，所以保存的应该是局部的最优分割点，那和我们结论中的就有些许出入了……不过不用担心，看代码我们可以发现 S[][] $S\left[\right]\left[\right]$ 的更新并不是通过自身来直接控制的，而是通过石子归并问题的状态转移方程的关系来控制的，也就是通过 dp[][] d p [ ] [ ] 之间的关系来左右的，所以，这样子保存最优分割点也变得可行了。

所以，如果设 k k 为区间 [i,j] $[i,j]$ 最优分割点，即 k=S[i][j] k = S [ i ] [ j ] ，那么 S[i][j−1]<=k<=S[i+1][j] S [ i ] [ j − 1 ] <= k <= S [ i + 1 ] [ j ] ，其中 S[][] S [ ] [ ] 的更新通过 dp[][] d p [ ] [ ] 的转移方程来控制。
.
接下来我们来看矩阵链乘的问题：

描述：

这个题求的是通过何种组合，可以使乘法次数最少……毕竟矩阵乘法复杂度真的很高，通过合理的组合减少乘法次数很有必要。

这两道题的题意几乎一致，只是状态转移方程略微不同，都是通过对一个固定序列进行类似于加括号的操作来改变运算顺序，区别就是运算规则不同而已。

此时，如果我们用四边形不等式优化来写的话，你会发现代码好一样啊，简直就是一个模子里抠出来的，那就看看代码吧~~~

代码：

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1004;

long long a[MAXN];
long long dp[MAXN][MAXN];
int S[MAXN][MAXN];

int main()
{
    int n;
    while (cin >> n)
    {
        int t = n + 1;
        for (int i = 1; i <= t; i++)
        {
            cin >> a[i];
        }

        for (int i = 1; i < t; i++)
        {
            S[i][i] = i;
        }

        for (int l = 2; l <= t; l++)
        {
            for (int i = 1; i + l - 1 <= t; i++)
            {
                int j = i + l - 1;
                dp[i][j] = INF;
                for (int k = S[i][j - 1]; k <= S[i + 1][j]; k++)
                {
                    long long q = dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j];
                    if (q < dp[i][j])
                    {
                        dp[i][j] = q;
                        S[i][j] = k;
                    }
                }
            }
        }

        cout << dp[1][n] << endl;
    }

    return 0;
}

不过此时，必须说的是，这个代码 WA W A 了！！！

Why??? W h y ? ? ?

可以明确的讲，状态转移方程没有问题，是四边形不等式优化导致的问题，明明两道题思路大相径庭，为何这个用四边形不等式优化就错了呢？

从另一个方面讲，如果石子归并的问题数据小一些，那么石子归并问题不用四边形不等式优化就能过，而矩阵链乘这个题数据小，不用不等式优化同样也能过，那么这两道题就真的没有什么分别了……

不过我们刚才讲过，两者真正的区别在于状态转移方程，石子归并问题的状态转移方程是：

而矩阵链乘的是：

这两个状态转移方程极为相似，我们可以理解为：

A A 是 dp[i][j] $dp\left[i\right]\left[j\right]$， D D 是 dp[i][k]+dp[k+1][j] $dp\left[i\right]\left[k\right]+dp[k+1]\left[j\right]$，而 Q Q 则是剩下的，记 Q1=W[i][j]，Q2=a[i−1]∗a[k]∗a[j] $Q_1=W\left[i\right]\left[j\right]，Q_2=a[i-1]\ast a\left[k\right]\ast a\left[j\right]$，也就是说区别在于 Q Q 。

此时我们来分析四边形不等式，这两道题的四边形不等式优化控制的是 k $k$ 的取值范围，能够保证在这个范围内，从 S[i][j−1] S [ i ] [ j − 1 ] 到 S[i+1][j] S [ i + 1 ] [ j ] 这个范围存在使 D D 最优的解，那么对于石子归并问题完全是可行的，因为 Q1 $Q_1$ 不管 k k 范围如何都是 W[i][j] $W\left[i\right]\left[j\right]$，根据代码我们可知， Q1 Q 1 是提前预处理好的一个二维数组的数据。不过， Q2 Q 2 可就不同了……

我们可以将 Q2 Q 2 看做是 a[k]∗(a[i−1]∗a[j]) a [ k ] ∗ ( a [ i − 1 ] ∗ a [ j ] ) ，如果将 a[k] a [ k ] 设为 x x ， a[i−1]∗a[j] $a[i-1]\ast a\left[j\right]$ 设为 Q3 Q 3 ，那么我们不难发现 Q3 Q 3 与 Q1 Q 1 是相似的，不受 k k 的影响的数据，而 Q2=xQ3 $Q_2=x{Q}_3$，而 x x 是受到了 k $k$ 影响的，所以虽然四边形不等式优化可以保证 D D 能够达到局部最优，也能保证 D+Q1 $D+Q_1$ 达到局部最优，但是却无法保证 D+Q2 D + Q 2 达到局部最优，因为 x x 受到了 k $k$ 范围缩小而带来的影响，那么动态规划到最后，经过四边形不等式优化的矩阵链乘问题自然是 WA W A 了。

早先在学四边形不等式优化时也是懵逼的狠，似懂非懂的做了石子归并问题，也没有考虑过很多，今天朋友忽然问到了这个问题，于是重新回过头审视了一番，发现自己曾经根本没有注意过这个问题，真是愚蠢至极。