Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

四边形不等式

洛水·锦依卫 2019-02-07 17:06:00 阅读数:253 评论数:0 点赞数:0 收藏数:0

Meaning

若有函数 \(a[i,j]\) ,令 \(i<i+1<=j<+1'\) ,若有:
\[ a[i][j]+a[i+1][j+1]\le a[i][j+1]+a[i+1][j] \]
则我们称函数 \(a\) 满足四边形不等式。

General

若我们在 \(DP\) 过程中会用到类似如下形式的方程:
\[ dp[i][j]=Min(dp[k][j]\ or\ dp[i][k]+dp[k+1][j])+w[i][j] \]
那么,只要代价函数 \(w\) 满足四边形不等式,那么函数 \(dp\) 一般也会满足四边形不等式。同时,假设 \(s[i][j]\) 为当 \(dp[i][j]\) 取得最优值的决策点,即:\(dp[i][j]=dp[s[i][j]]+w[i][j]\) ,一般 \(s\) 函数也会满足四边形不等式,这样,通过移项我们会得到:
\[ s[i+1][j]\le s[i][j]\le s[i][j-1] \]
或是:
\[ s[i][j-1]\le s[i][j]\le s[i+1][j] \]
那么我们选取决策点的转移范围就变小了,对于枚举决策点的复杂度为 \(O(n)\) 的转移方程,它的枚举复杂度经过均摊,这个 \(O(n)\) 将会变成常数级别,常常能使 \(n^3\)\(DP\) 降为 \(n^2\)

Example 1--石子合并

Problem

给你环形排列的 \(n\) 堆石子 \((n\le 100)\) ,第 \(i\) 堆石子数量为 \(a_i\) ,每次选择相邻的两堆合并,每次合并的代价将会是两堆石子的数量之和,问将所有石子合并成一堆的最大与最小代价分别是多少。

First Mentality

不难想到,首先断环为链,使之变成一条两倍长度的链,然后做 \(n^3​\) 的区间的 \(dp​\)

\(w[i][j]​\) 为区间 \([i-j]​\) 的石子数量之和, \(fmin[i][j],fmax[i][j]​\) 为合并区间 \([i-j]​\) 的最小、最大代价,初始状态为 \(fmin[i][i]=fmax[i][i]=0​\)

枚举 合并的区间长度 len (2~n)
枚举 合并区间的左端点 i (1~n)
枚举 区间合并点 j (i~i+len-2)
{
fmin[i][i+len-1]=Min(fmin[i][j]+fmin[j+1][i+len-1])+w[i][j]
fmax[i][i+len-1]=Max(fmax[i][j]+fmax[j+1][i+len-1])+w[i][j]
}

这样我们就得到了一个 \(n^3​\)\(dp​\) ,虽然对于题目来说确实够用了,但是如果 \(n\le 1000​\) 呢?这时候我们应该考虑如何优化。

最小代价四边形不等式优化

可以观察到 \(fmin​\) 的转移式满足使用四边形不等式的基本特征,同时,\(w​\) 函数也满足四边形不等式。那么,我们可以考虑使用四边形不等式了:

利用决策点的单调性 \(s[i][j-1]\le s[i][j]\le s[i+1][j]​\) 来优化第三层循环即可,初始状态为:\(s[i][i]=i​\)

枚举决策点转移时同时更新 \(s[i][j]\) 来决策就好。

最大代价决策点优化

首先有这样一个结论:\(f[i][j]\) 的最优决策点必定在 \(i\)\(j-1\) 两者之间。

考虑如何证明,反证法奉上:

\(w[i][p]\)\(w[p+1][j]\) 的差值函数为 \(S=w[i][p]-w[p+1][j]\) ,可以观察到此函数单峰。

  • 对于 \(S>=0\) 的情况:

若最优决策点为 \(i< p< j-1\) ,我们设 \(s[p+1][j]=k\) ,那么相应转移方程为:
\[ f[i][j]=f[i][p]+f[p+1][k]+f[k+1][j]+w[p+1][j]+w[i][j] \]
对应的,我们的合并方案为:
\[ (a[i],a[i+1],...,a[p])U((a[p+1],a[p+2],...,a[k])U(a[k+1],a[k+2],...,a[j])) \]
那么我们考虑另一种合并方式:
\[ ((a[i],a[i+1],...,a[p])U(a[p+1],a[p+2],...,a[k]))U(a[k+1],a[k+2],...,a[j]) \]
则对应的转移方程为:
\[ f[i][j]=f[i][p]+f[p+1][k]+f[k+1][j]+w[i][p]+\sum_{l=p+1}^ja[l] +w[i][j] \]
由于另一种合并方式必定比原决策更优,即选取决策点 \(k\) 优于 \(p\)\(k>p\) ,由于函数 \(S\)\(>=0\) 右侧区间单调递增,则若选取决策点为 \(p\)\(S>=0\)\(p<j-1\) ,那么总有选取 \(k=s[p+1][j]>p\) 优于 \(p\) ,那么由此可知对于某个决策点 \(q\) 往右的决策必定单调变优。则对于所有 \(p>q\) ,选取 \(p=j-1\) 将会最优。

  • 对于 \(S<0\)

类似的,设最优决策点为 \(i<p<j-1\) ,我们设 \(s[i][p]=k\) ,那么对应值为:
\[ f[i][k]+f[k+1][p]+f[p+1][j]+w[i][p]+w[i][j] \]
同样,我们考虑另一种合并方式:合并 \([i,k]([k+1,p][p+1,j])\) ,则此时的值为
\[ f[i][k]+f[k+1][p]+f[p+1][j]+w[p+1][j]+w[i][j]+\sum_{l=k+1}^pa[l] \]
则另一种必定优于原本的决策。

那么对于上面的决策点 \(q\) 往左的决策必定单调变优,因为对于任意 \(p>i\)\(S<0\) 都必定有决策点 \(k=s[i][p]<p\) 要更优,则在左端点选取 \(p=i\) 最优。

得证,故转移决策点仅需在 \(i\)\(j-1\) 之间选取。

Code

重点看 \(dp\) 就好 = =。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[101],fmax[201][101],posi[201][101],fmin[201][101],maxans,minans;
int main()
{
cin>>n;
memset(fmin,0x7f,sizeof(fmin));
minans=2e9;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++)a[i]+=a[i-1],fmin[i][i]=0,posi[i][i]=i;//初始化 dp 数组与 决策点
for(int i=1;i<n;i++)
for(int j=1;j<=2*n-i;j++)
{
fmax[j][j+i]=max(fmax[j][j+i-1],fmax[j+1][j+i])+a[j+i]-a[j-1];//两个端点取最优
for(int k=posi[j+1][j+i];k>=posi[j][j+i-1];k--)
if(fmin[j][j+i]>0ll+fmin[j][k]+fmin[k+1][j+i]+a[j+i]-a[j-1])
fmin[j][j+i]=fmin[j][k]+fmin[k+1][j+i]+a[j+i]-a[j-1],posi[j][j+i]=k;//四边形不等式优化后的决策点枚举
}
for(int i=1;i<=n;i++)
{
minans=min(minans,fmin[i][i+n-1]);
maxans=max(maxans,fmax[i][i+n-1]);
}
cout<<minans<<endl;
cout<<maxans;
}

Example 2--山区建小学

Problem

一条直线上分布着 \(n\) 个村子 \((n\le 500)\) ,第 \(i\) 个村子距离第 \(i+1\) 个村子的距离为 \(a_i\) ,要求在 \(n\) 个村子中选取 \(m\) 个建造小学 \((m\le n)\) ,使得所有村子到距离它最近的小学的距离和最小。输出最小距离和。

First Mentality

一道很经典的 \(DP\) 题。设 \(w[i][j]\) 为在村庄 \(i-j\) 中只建立一个小学,所有村庄到这个小学的最小距离和。而这个最小距离和的位置必定为最中间的那个村庄,这也是一个经典的数学证明,即中位数为最小距离和的位置。

\(f[i][j]\) 为对于前 \(i\) 个村庄建立 \(j\) 个小学的最小距离和,那么转移方程为:
\[ f[i][j]=Min(f[k][j-1]+w[k+1,i]) \]
\(w\) 函数只需要勤记前缀和即可转移时 \(O(1)\) 求出。

不用疑惑为什么这样转移没有考虑第 \(k+1-i\) 个村庄中为什么不会有到前 \(k\) 个村庄的小学距离更短的村庄,因为这样反正不会影响答案使之变劣。

四边形不等式优化

经过大眼 or 打表观察法, 我们发现 \(w\) 函数又满足四边形不等式!那么我们假设 \(s[i][j]\)\(f[i][j]\) 的最优决策点,即 \(f[i][j]=f[s[i][j]][j-1]+w[s[i][j]+1][i]\) ,我们同样可以猜想套路:
\[ s[i-1][j]\le s[i][j]\le s[i+1][j] \]
那么初始化为:

\(f[i][1]=w[1][i],s[i][1]=(i+1)>>1,s[n+1][i]=n\)

完毕。

Code

\(dp\) 才是重点,码风比较仙。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,d[501],q[501],h[502],f[501][501],pos[502][501],inf=1e9;
int work(int l,int r)
{
int mid=(l+r)>>1;
return h[l]-h[mid]-(mid-l)*(h[mid]-h[mid+1])+q[r]-q[mid]-(r-mid)*(q[mid]-q[mid-1]);
}//w 函数计算
int main()
{
cin>>n>>m;
for(int i=2;i<=n;i++)
{
scanf("%d",&d[i]);
q[i]=d[i],h[i-1]=d[i];
}
for(int l=1;l<=2;l++)for(int i=1;i<=n;i++)q[i]+=q[i-1];//初始化前缀和的前缀和
for(int l=1;l<=2;l++)for(int i=n;i>=1;i--)h[i]+=h[i+1];//初始化后缀和的后缀和
for(int i=1;i<=n;i++)f[i][1]=work(1,i),pos[i][1]=0;//初始化 dp 数组与决策点
for(int j=2;j<=m;j++)
{
pos[n+1][j]=n;
for(int i=n;i>j;i--)//由于四边形不等式需要,我们从大到小枚举 i
{
f[i][j]=inf;
for(int k=pos[i][j-1];k<=pos[i+1][j];k++)
{
int tmp=f[k][j-1]+work(k+1,i);
if(tmp<f[i][j])
f[i][j]=tmp,pos[i][j]=k;
}
}
}
cout<<f[n][m];
}

总结

四边形不等式是一个套路,虽然不常见,但是应熟记于心以防万一。

同时,考场上要通过数学证明函数满足四边形不等式其实还是蛮困难的,建议不要头铁,打打表证明就好了= = 。

版权声明
本文为[洛水·锦依卫]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/luoshuitianyi/p/10354956.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)