区间DP+平行四边形优化总结
区间DP形式模板:
|
for(i = 1;i <= n;i++) dp[i][i] = 初始值; for(len = 2;len <= n;len++){ for(i = 1;i <= n;i++){ j = i + len - 1; if(j > n)break; for(k = i;k < j;k++) dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]); } }
|
平行四边形优化:
我们不难发现上面的复杂度为$O(n^3)$,通过平行四边形优化,可以将第三维枚举(枚举最优分割点)的范围大大缩小。
定理:二位决策单调性
在转移方程$F[i,j]=min_{i\leq k<j} {F[i,k]+F[k+1,j]+w(i,j)}$中,记$P[i]$为令$F[i,j]$取到最小值的K值。
如果F满足四边形不等式,那么对于任意$i<j$,有$P[i,j-1]\le P[i,j]\le P[i+1,j]$.
优化:
$P[i,j-1]\le P[i,j]\le P[i+1,j]$作为第三维的范围,这样就缩小了寻找最优分割点的次数
区间DP+四边形优化板子:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
for(i = 1;i <= n;i++){ dp[i][i] = 初始值; s[i][i] = i; } for(len = 2;len <= n;len++){ for(i = 1;i <= n;i++){ j = i + len - 1; if(j > n)break; for(k = s[i][j - 1];k < s[i + 1][j];k++) if(dp[i][j] > dp[i][k] + dp[k + 1][j] + w[i][j]){ dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j]; s[i][j] = k; } } }
|
例题:HDU3561 Tree Construction
http://acm.hdu.edu.cn/showproblem.php?pid=3516
转移方程:$dp[i][j]=min { dp[i][k-1]+dp[k][j] + dis(uni(i,k-1),uni(k,j))}$
其中$dp[i][j]$表示从$i$到$j$的最优解,$dis(i,j)$表示$i$和$j$之间的曼哈顿距离,$uni(i,j)$表示将$i$和$j$用平行于坐标轴的线段连在一起时的拐角点。
然后可以证明这是满足四边形优化条件的。
然后四边形优化一下就好。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=100000000; int dp[1000+5][1000+5]; int s[1000+5][1000+5]; int x[1000+5],y[1000+5]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d%d",&x[i],&y[i]); } for(int i=1;i<=1000+2;i++) { s[i][i]=i;dp[i][i]=0;} for(int len=1;len<=n;len++) { for(int l=1;l+len<=n;l++) { int r=l+len; dp[l][r]=inf; for(int k=s[l][r-1];k<=s[l+1][r];k++) { if(dp[l][k]+dp[k+1][r]+abs(x[k+1]-x[l])+abs(y[k]-y[r])<=dp[l][r]) { dp[l][r]=dp[l][k]+dp[k+1][r]+abs(x[k+1]-x[l])+abs(y[k]-y[r]); s[l][r]=k; } } } } printf("%d\n",dp[1][n]); } return 0; }
|