四边形不等式优化dp

对于转移方程 \(c(i,j)=w(i,j)+\min_d(c(i,d)+c(d+1,j))\)，存在 \(w(i,j)+w(i',j')\le w(i,j')+w(i',j)(i\le i'\le j\le j'\) 如何快速求其答案。

引理一：\(w(i,j)+w(i',j')\le w(i,j')+w(i',j)\) 则 \(c(i,j)+c(i',j')\le c(i,j')+c(i',j)\)，记 \(x(i,j)=\min_d(c(i,d)+c(d+1,j))\)，只要 \(x\) 满足 \(x(i,j)+x(i',j')\le x(i,j')+x(i',j)\) 即可。

假设条件对 \(len<j'-i+1\) 的任意 \(len\) 成立，那么：我们只需要证明，\(x(i,j')\) 和 \(x(i',j)\) 的任意拆分方式，\(x(i,j)\) 和 \(x(i',j')\) 都存在不更劣的拆分即可。考虑 \(x(i,j'),x(i',j)\) 的决策点 \(k,l\) 在哪里，首先只处理 \(k\le l\)。然后假设 \(x(i,j')\) 被拆分成 \(c(i,k)\) 和 \(c(k+1,j')\)，\(x(i',j)\) 被拆分成 \(c(i',l)\) 和 \(c(l+1,j)\)，那么我们同时把对面拆分成 \(c(i,k)\) 和 \(c(k+1,j)\) 以及 \(c(i',l)\) 和 \(c(l+1,j')\)。

那么两边 \(c(i,k)+c(i',l)\) 抵消，变成了 \(c(k+1,j')+c(l+1,j)\) 和 \(c(k+1,j)+c(l+1,j')\)，因为 \(k+1\le l+1\le j\le j'\)，所以只要证明这个就可以了。而一开始的数学归纳决定了对 \(len<j'-i+1\) 的任意 \(len\) 成立，而 \(k+1>i\)，所以成立。这种情况我们是抵消左边，对于 \(k>l\) 抵消右边即可。

引理2：\(c(i,j)\) 满足四边形不等式，则使得 \(c(i,j)\) 取得最小值的最大决策点 \(k(i,j)\) 满足 \(k(i,j)\le k(i,j+1)\le k(i+1,j+1)\)。

先证明 \(k(i,j)\le k(i,j+1)\)，设两者分别为 \(a,b\)，那么如果 \(a>b\)，则

因为我们在 \((i,j+1)\) 没有决策 \(a\)，所以 \(c(i,a)+c(a+1,j+1)>c(i,b)+c(b+1,j+1)\)。
因为我们在 \((i,j)\) 没有决策 \(b\)，所以 \(c(i,b)+c(b+1,j)\ge c(i,a)+c(a+1,j)\)。

两式相加 \(c(a+1,j+1)+c(b+1,j)>c(b+1,j+1)+c(a+1,j)\)。
但是因为 \(b+1<a+1\le j<j+1\)，所以根据四边形不等式条件有 \(c(a+1,j+1)+c(b+1,j)>c(b+1,j+1)+c(a+1,j)\)，矛盾，所以 \(a\le b\)。

然后证明 \(k(i,j)\le k(i+1,j)\)，设两者分别为 \(a,b\)，那么如果 \(a>b\)，则

因为我们在 \((i,j)\) 没有决策 \(b\)，所以 \(c(i,b)+c(b+1,j)\ge c(i,a)+c(a+1,j)\)。
因为我们在 \((i+1,j)\) 没有决策 \(a\)，所以 \(c(i+1,a)+c(a+1,j)>c(i+1,b)+c(b+1,j)\)。

两式相加 \(c(i,b)+c(i+1,a)>c(i,a)+c(i+1,b)\)。但是因为 \(i<i+1\le b<a\)，所以 \(c(i,b)+c(i+1,a)\le c(i,a)+c(i+1,b)\)，矛盾，得证 \(a\le b\)。

则引理二得证：\(c(i,j)\le c(i,j+1)\le c(i+1,j+1)\)。

所以，我们得到在决策矩阵上行和列都是单调的。

那么，我们计算 \(c(i,j)\) 的时候只需要计算 \([k(i,j-1),k(i+1,j)]\) 内的决策点即可。这里的复杂度是 \(\sum_{1\le i<j\le n}k(i+1,j)-\sum_{1\le i<j\le n}k(i,j-1)+n^2\)
\(=\sum_{1<i'\le j\le n}k(i',j)-\sum_{1\le i\le j'<n}k(i,j')\)
\(=\sum_{1<i\le n} k(i,n)-\sum_{1\le j<n}k(1,j)\le n^2\)。

我们也就得到了 dp 的四边形不等式优化方法。