四边形不等式学习笔记

简要题意

四边形不等式是一种 dp 优化策略。多用于 2D DP。

内容

对于区间 \([l,r]\) 带来的贡献 \(w(l,r)\),如果其满足:

对于 \(L\leq l\leq 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\)):

\[f(i,j)=\min_{k=1}^{i-1}{(f(k,j-1)+w(k+1,j))} \]

\(w\) 满足四边形不等式。则:

  • \(f\) 也满足四边形不等式。
  • \(f\) 满足四边形不等式基础。

SPOJ LARMY - Lannister Army

给出一个长为 \(N\) 的序列 \(H\),你需要将其分成 \(K\) 段,使得每一段的逆序对数量之和最小。输出最小值。

\(1 \leq K \leq N \leq 5\times10^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 2\rfloor}\)

然后,然后就没了。

时间复杂度 \(O(V^2)\)

类型二

对于一类区间 dp 问题(多见于石子合并类),其状态转移方程为(\(\min\) 也可以换成 \(\max\)):

\[f(i,j)=\min_{k=i}^{j-1}{(f(i,k)+f(k+1,j)+w(i,j))} \]

\(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)\)

热门相关:帝少的专属:小甜心,太缠人   第一神算:纨绔大小姐   寂静王冠   敦伦睦邻2   天启预报