四边形不等式优化
四边形不等式定义
在oi历程中，常有如下的dp转移方程
\(f(i,j)=min(f(i,k)+f(k+1,j)+w(i,j))\) \((i<=k<j)\)
\(f(i,j)=inf\) \((i>j)\)
\(f(i,j)=0\) \((i==j)\)
根据转移，可以看出这是个\(O(n^3)\)的时间复杂度
但是 我们可以根据一些性质，优化部分转移，使其时间复杂度将至\(O(n^2)\)
四边形不等式的定义
如函数\(w\)，满足
\(w(i,j')+w(i',j)>= w(i,j)+w(i',j')\) \((i<=i'<j<=j')\)
则称\(w\)是满足四边形不等式的，或称具有凸完全单调性
可记作：交叉小于包含
性质
- 若形同上式的\(dp\)方程中，\(w\)函数满足凸完全单调性，则\(f\)也满足凸完全单调性
证明
当\(i==i'\)或\(j==j'\)时
显然成立
------------
当\(i<i'=j<j'\)时
原式=\(w(i,j')+w(j,j') <= w(i,j')\)
设\(k=min(t)(f(i,j')=f(i,t)+f(t+1,j')+w(i,j'))\)
由于对称性(即下文中不等号右面的\(j\)，\(k\)可以互换)，则设\(k<=j\)
有
\(f(i,j)+f(j,j')<=f(i,j)+f(k+1.j)+w(i,j)+f(j,j')+w(j,j')\) (因为是最有决策，不等号成立)
\(f(i,j)+f(j,j')<=f(i,j')\)
利用数学归纳法得证
------------
当\(i<i'<j<j'\)时
设\(y=min(t)(f(i',j)=f(i,t)+f(t+1,j')+w(i,j'))\)
设\(z=min(t)(f(i,j')=f(i',t)+f(t+1,j)+w(i',j))\)
由于对称性(同上),可以设\(z<=y\)
\[f(i,j)+f(i',j')<=w(i,j)+w(i',j')+f(i',y)+f(i,z)+f(y+1,j')+f(z+1,j)\];
\[<=w(i,j)+w(i',j')+f(i',y)+f(i,z)+f(z+1,j')+f(y+1,j)\];
\[=f(i,j')+f(i',j)\];
为什么这个东西成立呢？
因为他的成立的必要条件是\(f(i',y)+f(i,z)+f(y+1,j')+f(z+1,j)<=f(i',y)+f(i,z)+f(z+1,j')+f(y+1,j)\)
可以看做是上述问题的规模缩小版。其最终情况会回归到前两种情景。
- 决策单调性
我们加速dp所使用的就是决策单调性，四边形不等式是为了引出他
设s(i,j)为f(i,j)的最有决策点
那么有
\(s(i,j)<=s(i,j+1)<=s(i+1,j+1)\)
证明
在\(i>j\) 时
显然成立
-----------------
在\(i<j\)时为了方便叙述，我们令\(f_k(i,j)\)表示\(f(i,j)\)在\(k\)时的决策值
有\(f_{s(i,j)}(i,j)=f(i,j)\)由于f满足四边形不等式
所以有
\(f(k,j)+f(k',j+1)<=f(k,j+1)+f(k',j) (k<k'<j)\)
在不等式两边加上\(w(i,j)+f(i,k-1)+w(i,j+1)+f(i,k'-1)\)
便可得出
\(f_k(i,j)+f_{k'}(i,j+1) <= f_k(i,j+1)+f_{k'}(i,j)\)
即\(f_k(i,j)-f_{k'}(i,j)<=f_k(i,j+1)-f_{k'}(i,j+1)\)可以发现，可以由左式推出右式
由于在\(s(i,j)\)右边的决策点来说，必有\(f_k(i,j)>=f(i,j)\)
还一定有 \(f_s(i,j)(i,j+1)<=f_k(i,j+1)\)
当然，\(f(i,j)\)的决策点不一定是\(s(i,j)\)
但通过我们上面的证明，便可以确定，一定不小于\(s(i,j)\)
便证明出来了\(s(i,j)<=s(i,j+1)\)
剩下的一对也可以如此证明
若\(s\)满足上面的关系.则称s关于区间包含关系单调
好（AO） 结束了上面的证明，便可以运用到\(dp\)中去了
这玩意写了我一个晚上qwq，为了保证正确性，边写边证
我们只需要处理这个决策点就可以啦
根据证明，在确定一个大区间\([i,j]\)时，\([i,j-1]\)和\([i+1,j]\)的最有决策点已经确定了。直接在范围内枚举就好了
关于时间复杂度么，不会证
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::max;
using std::min;
const int maxn=300;
int base[maxn];
int dp[maxn][maxn],s[maxn][maxn];
int MAX[maxn][maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&base[i]);
base[i+n]=base[i];
}
for(int i=1;i<=n*2;i++)
base[i]+=base[i-1];
for(int i=1;i<=n*2;i++)
s[i][i]=i;
for(int l=2;l<=n;l++)
for(int i=1;i<=(n*2)-l+1;i++)
{
int j=i+l-1;
int x=s[i][j-1],y=s[i+1][j];
dp[i][j]=0x7fffffff;
MAX[i][j]=max(MAX[i][j-1],MAX[i+1][j])+base[j]-base[i-1];//最大值不满足四边形不等式，但最有决策一定出现在端点处
for(int k=x;k<=y;k++)
if(dp[i][k]+dp[k+1][j]+base[j]-base[i-1]<dp[i][j])
{
dp[i][j]=dp[i][k]+dp[k+1][j]+base[j]-base[i-1];
s[i][j]=k;
}
}
int ansMin=0x7fffffff,ansMax=0;
for(int i=1;i<n;i++)
ansMin=min(ansMin,dp[i][i+n-1]),
ansMax=max(ansMax,MAX[i][i+n-1]);
printf("%d\n%d",ansMin,ansMax);
return 0;
}