[HDU 3506]Monkey Party


Description

题库链接

长度为 \(n\) 的环状石子合并。

\(1\leq n\leq 1000\)

Solution

假设有区间 DP 的转移方程是 \(f_{l,r}=\min(\max)\{f_{l,k}+f_{k+1,r}+w(l,r)\}\),如果 \(w\) 满足四边形不等式以及区间单调性,那么这个式子是可以利用某些单调性优化到 \(O(n^2)\) 的。

  • 四边形不等式,还是以 \(\forall a,b,c,d, a\leq b\leq c\leq d, w(a,d)+w(b,c)\geq w(a,c)+w(b,d)\) 为例。
  • 区间单调性,即 \(\forall a,b,c,d, a\leq b\leq c\leq d, w(a,d)\geq w(b,c)\),即小区间的函数值不超过包含其的大区间。并且式中的不等号应时刻与四边形不等式的不等号方向一致。

对于不等号的方向和取 \(\min\) 还是取 \(\max\) 之间的关系,这里要说明的是当上述不等号取 \(\geq\) 时,对应的 DP 方程是要取 \(\min\) 的,并且单调性与枚举顺序相同。

先不加证明地引出两个引理。(不证明是考虑到引理证出来意义不大,并且没有必要。如果你感兴趣可以参考《动态规划加速原理之四边形不等式(赵爽)》这篇文章)

引理一 对于 DP 方程,\(f_{l,r}=\min\{f_{l,k}+f_{k+1,r}+w(l,r)\}\),若 \(w\) 满足四边形不等式和区间单调性,那么 DP 函数 \(f\) 同样满足四边形不等式。

引理二\(s_{l,r}\)\(f_{l,r}\) 的最优决策点。如果 \(f\) 满足四边形不等式,那么会有 \(s_{i,j}\leq s_{i,j+1}\leq s_{i+1,j+1}\)

四边形不等式定理 若利用引理二的单调性,即 \(s_{i,j-1}\leq s_{i,j}\leq s_{i+1,j}\),来优化该区间 DP,其复杂度是可以降低至 \(O(n^2)\) 的。

证明:从区间 DP 的本质入手,我们考虑当区间长度为 \(\delta\) 时枚举的量。对于每个左端点:
\(l=1\)\((l,l+\delta-1)\) 枚举长度是 \(s_{l+1,l+\delta-1}-s_{l,l+\delta-2}=s_{2,\delta}-s_{1,\delta-1}\)
\(l=2\),枚举长度是 \(s_{3,1+\delta}-s_{2,\delta}\)
\(l=3\),枚举长度是 \(s_{4,2+\delta}-s_{3,1+\delta}\)
\(\vdots\)
\(l=n+1-\delta\),枚举长度是 \(s_{n+2-\delta,n}-s_{n+1-\delta,n-1}\)
把上式相加,总长度是 \(s_{n+2-\delta,n}-s_{1,\delta-1}\leq n\)。又由于总共有 \(n\) 个不同的 \(\delta\),因此总复杂度为 \(O(n^2)\)

更多内容可见四边形不等式定理优化。

Code

#include 
#define ll long long
#define w(l, r) (a[r]-a[l-1])
using namespace std;
const int N = 2005;

int n, a[N], s[N][N];
ll f[N][N];

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), a[i+n] = a[i];
        n <<= 1;
        for (int i = 1; i <= n; i++) a[i] += a[i-1];
        for (int i = 1; i <= n; i++)
            f[i][i] = 0, s[i][i] = i;
        for (int i = 2, m = n>>1; i <= m; i++)
            for (int l = 1, r; (r = l+i-1) <= n; l++) {
                f[l][r] = 1e15;
                for (int k = s[l][r-1]; k <= s[l+1][r]; k++)
                    if (k < r && f[l][r] > f[l][k]+f[k+1][r]+w(l, r)) {
                        f[l][r] = f[l][k]+f[k+1][r]+w(l, r);
                        s[l][r] = k;
                    }
            }
        ll ans = 1e15;
        for (int i = 1, m = n>>1; i <= m; i++)
            ans = min(ans, f[i][i+m-1]);
        printf("%lld\n", ans);
    }
    return 0;
}