簡要題意
四邊形不等式是一種 dp 優(yōu)化策略。多用于 2D DP。
內(nèi)容
對于區(qū)間 \([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\) 滿足四邊形不等式。特別地，如果上式符號取等，則稱其滿足四邊形恒等式。
注：上面的不等式可以記成：交叉小于包含。
四邊形不等式優(yōu)化基礎：對于一個 dp \(f(i,j)\)，如果其最優(yōu)決策點（即第三維枚舉的最優(yōu)位置） \(s(i,j)\) 滿足 \({s(i,j-1)\leq s(i,j) \leq s(i+1,j)}\)，則可以用此方法將時間復雜度優(yōu)化到 \(O(\max i \cdot \max j)\)。
類型一
對于一類 dp（多見于把一個序列分成 \(k\) 段，最小化或最大化每一段段貢獻的的和），其狀態(tài)轉移方程為（\(\min\) 也可以換成 \(\max\)）：
且 \(w\) 滿足四邊形不等式。則：
- \(f\) 也滿足四邊形不等式。
- \(f\) 滿足四邊形不等式基礎。
SPOJ LARMY - Lannister Army
給出一個長為 \(N\) 的序列 \(H\)，你需要將其分成 \(K\) 段，使得每一段的逆序?qū)?shù)量之和最小。輸出最小值。
\(1 \leq K \leq N \leq 5\times10^3,1 \leq H_i \leq 10^5\)
不能再板的四邊形不等式吧。先推出每一個序列的每一個區(qū)間的逆序?qū)?shù)量，然后四邊形不等式即可。
時間復雜度 \(O(N^2)\)。文章來源地址http://www.zghlxwxcb.cn/news/detail-409603.html
P4767 [IOI2000]郵局
在數(shù)軸上分布著 \(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)\)。
類型二
對于一類區(qū)間 dp 問題（多見于石子合并類），其狀態(tài)轉移方程為（\(\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)\) 前綴和 + 區(qū)間 DP 可以過，但是容易發(fā)現(xiàn) \(w(i,j)=\sum_{k=i}^{j} m_k\) 滿足四邊形不等式。于是可以使用四邊形不等式優(yōu)化。文章來源：http://www.zghlxwxcb.cn/news/detail-409603.html
時間復雜度 \(O(N^2)\)。
到了這里，關于四邊形不等式學習筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
