[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;
}