四边形不等式优化
四边形不等式定义
在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
%d",ansMin,ansMax);
return 0;
}