简要题意
四边形不等式是一种 dp 优化策略。多用于 2D DP。
内容
对于区间 ([l,r]) 带来的贡献 (w(l,r)),如果其满足:
对于 (Lleq lleq r leq R),(w(L,r)+w(l,R)leq w(L,R)+w(l,r))
则称 (w) 满足四边形不等式。特别地,如果上式符号取等,则称其满足四边形恒等式。
注:上面的不等式可以记成:交叉小于包含。
四边形不等式优化基础:对于一个 dp (f(i,j)),如果其最优决策点(即第三维枚举的最优位置) (s(i,j)) 满足 ({s(i,j-1)leq s(i,j) leq s(i+1,j)}),则可以用此方法将时间复杂度优化到 (O(max i cdot max j))。
类型一
对于一类 dp(多见于把一个序列分成 (k) 段,最小化或最大化每一段段贡献的的和),其状态转移方程为((min) 也可以换成 (max)):
]
且 (w) 满足四边形不等式。则:
- (f) 也满足四边形不等式。
- (f) 满足四边形不等式基础。
SPOJ LARMY – Lannister Army
给出一个长为 (N) 的序列 (H),你需要将其分成 (K) 段,使得每一段的逆序对数量之和最小。输出最小值。
(1 leq K leq N leq 5times10^3,1 leq H_i leq 10^5)
不能再板的四边形不等式吧。先推出每一个序列的每一个区间的逆序对数量,然后四边形不等式即可。
时间复杂度 (O(N^2))。
P4767 [IOI2000]邮局
在数轴上分布着 (V) 个村庄。第 (i) 个村庄在 (a_i)。两个村庄的距离为这两个村庄的位置之差得绝对值。你需要在一些村庄中修建邮局,你需要输出每一个村庄到离其最近的邮局的距离之和的最小值。
(1 leq P leq 300,1 leq P leq V leq 3 times 10^3,1 leq a_i leq 10^4)
这道题可以看成将村庄排序后分成 (P) 段,每段在其中点修建一个邮局。最小化每段到其中点的距离和的和。
可以递推出每段的贡献 (w(i,j)=w(i-1,j)+a_j-a_{lfloor (i+j)div 2rfloor})。
然后,然后就没了。
时间复杂度 (O(V^2))。
类型二
对于一类区间 dp 问题(多见于石子合并类),其状态转移方程为((min) 也可以换成 (max)):
]
且 (w) 满足四边形不等式。则:
- (f) 也满足四边形不等式。
- (f) 满足四边形不等式基础。
P1775 石子合并(弱化版)
有一个长度为 (N) 的序列 (m)。你可以合并相邻的两个元素 (m_i,m_j),变成 (m_i+m_j),并花费 (m_i+m_j) 的代价。输出最小代价和。
(1 leq N leq 300,1 leq m_i leq 10^3)
这道题暴力 (O(N^3)) 前缀和 + 区间 DP 可以过,但是容易发现 (w(i,j)=sum_{k=i}^{j} m_k) 满足四边形不等式。于是可以使用四边形不等式优化。
时间复杂度 (O(N^2))。
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net