动态规划之四边形不等式优化

四边形不等式

设函数\(w(x,y)\)是定义在\(Z\)上的函数,若对于任意\(a,b,c,d \in Z\),其中\(a\leq b \leq c \leq d\), 都有\(w(a,d)+w(b,c)\ge w(a,c)+w(b,d)\),则称函数\(w\)满足四边形不等式

推论:

设函数\(w(x,y)\)是定义在\(Z\)上的函数,若对于任意\(a,b \in Z\),其中\(a<b\), 都有\(w(a,b+1)+w(a+1,b) \ge w(a,b)+w(a+1,b+1)\),则函数\(w\)满足四边形不等式

证明:

对于\(a<c\),有:
\[ w(a,c+1)+w(a+1,c) \ge w(a,c)+w(a+1,c+1) \]
对于\(a+1<c\),有:
\[ w(a+1,c+1)+w(a+2,c) \ge w(a+1,c)+w(a+2,c+1) \]
两式相加,得:
\[ w(a,c+1)+w(a+1,c)+w(a+1,c+1)+w(a+2,c)\ge w(a,c)+w(a+1,c+1)\\ +w(a+1,c)+w(a+2,c+1) \]
整理得:
\[ w(a,c+1)+w(a+2,c)\ge w(a,c)+w(a+2,c+1) \]
依此类推,对于任意\(a\leq b \leq c\),有:
\[ w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1) \]
(此处即用\(b\)来代替\(a+2\),因为\(a+1 <c\) ,所以\(b \leq c\))

同理,对于任意\(a\leq b \leq c \leq d\),有:
\[ w(a,d)+w(b,c)\ge w(a,c)+w(b,d) \]

定理1

对于任意\(a,b,c,d \in Z\),如果函数\(w\)满足四边形不等式,且\(w(a,d)\ge w(b,c)\),则函数\(f\)也满足四边形不等式,其中\(f\)满足:
\[ f(x,y)=min(f(x,z)+f(z+1,y)+w(x,y)|x\leq z <y) \]
(特别的,我们令\(f(x,y)=w(x,y)=0\))

证明:

当\(x+1=y\)时,我们有:
\[ f(x,y+1)+f(x+1,y)=f(x,x+2)+f(x+1,x+1)=f(x,x+2) \]
若\(f(x,x+2)\)的最优决策是\(x+1\),则:
\[ f(x,x+2)=f(x,x+1)+f(x+2,x+2)+w(x,x+2)=w(x,x+1)+w(x,x+2) \]
显然
\[ w(x,x+1)+w(x,x+2)\ge w(x,x+1)+w(x+1,x+2) \]
若\(f(x,x+2)\)的最优决策是\(x\),则:
\[ f(x,x+2)=f(x,x)+f(x+1,x+2)+w(x,x+2)=w(x+1,x+2)+w(x,x+2) \]
显然
\[ w(x+1,x+2)+w(x,x+2)\ge w(x+1,x+2)+w(x,x+1) \]

\[ w(x,x+1)+w(x+1,x+2)=f(x,x+1)+f(x+1,x+2)=f(x,y)+f(x+1,y+1) \]
所以当\(x+1=y\) 时,我们得到:
\[ f(x,y+1)+f(x+1,y)\ge f(x,y)+f(x+1,y+1) \]
即此时四边形不等式成立。

接下来,我们运用数学归纳法

假设当\(y-x<k\)时,四边形不等式成立。

我们现在考虑\(y-x=k\)的情况

令\(f(x,y+1)\)以\(a\)为最优决策,\(f(x+1,y)\)以\(b\)为最优决策。

不妨设\(x+1\leq a \leq b\)

易得:
\[ f(x,y+1)+f(x+1,y)=f(x,a)+f(a+1,y+1)+w(x,y+1)\\ +f(x+1,b)+f(b+1,y)+w(x+1,y) \]
对于\(f(x,y)\)和\(f(x+1,y+1)\),由于\(a\),\(b\)不一定是最优决策,所以我们有:
\[ f(x,y)+f(x+1,y+1)\le f(x,a)+f(a+1,y)+w(x,y)\\ +f(x+1,b)+f(b+1,y+1)+w(x+1,y+1) \]
因为\(w\)满足四边形不等式,所以:
\[ w(x,y+1)+w(x+1,y)\ge w(x,y)+w(x+1,y+1) \]
根据归纳假设,我们有:
\[ f(a+1,y+1)+f(b+1,y)\ge f(a+1,y)+f(b+1,y+1) \]
于是我们有:
\[ f(x,y+1)+f(x+1,y)\ge f(x,y)+(x+1,y+1) \]

定理2:

对于任意\(a,b,c,d \in Z\),如果函数\(w\)满足四边形不等式,且函数\(f\)满足:
\[ f(x,y)=min(f(x,z)+f(z+1,y)+w(x,y)|x\leq z <y) \]
(特别的,我们令\(f(x,y)=w(x,y)=0\))

记\(P(x,y)\)为令\(f(x,y)\)取到最小值的\(k\)值。如果函数\(f\)满足四边形不等式,那么对于任意\(x\),\(y\),我们有:
\[ P(x,y-1)\leq P(x,y)\leq P(x+1,y) \]
证明:

记\(p=P(i,j)\)。

对于任意的\(x< k \leq p\),由四边形不等式得:
\[ f(x,t)+f(x+1,k)\ge f(x,k)+f(x+1,t) \]
移项得:
\[ f(x+1,k)-f(x+1,t)\ge f(x,k)-f(x,t) \]
由于\(p\)为最优决策,所以我们有:
\[ f(x,k)+f(k+1,y)\ge f(x,p)+f(p+1,y) \]
所以:
\[ \begin{array}{lcr} (f(x+1,k)+f(k+1,y)+w(x+1,y))-(f(x+1,p)+f(p+1,y)+w(x+1,y))\\ =(f(x+1,k)-f(x+1,p))+(f(k+1,y)-f(p+1,y)) \\ \ge (f(x,k)-f(x,p))+(f(k+1,y)-f(p+1,y)) \\ =(f(x,k)+f(k+1,y))-(f(x,p)+f(p+1,y))\\ \ge 0 \end{array} \]
这意味着,对于\(f(x+1,y)\) 的任意决策\(k\leq p\),\(p\)都要比\(k\)更优(包括相等)

所以
\[ P(x+1,y)\ge P(x,y) \]
同理可证
\[ P(x,y-1)\leq P(x,y) \]
所以
\[ P(x,y-1)\leq P(x,y) \leq P(x+1,y)) \]

例题

1.[NOI1995]石子合并

现在有\(n\)堆石子(环状), 每次只能将相邻的两堆合并成一堆,每次的得分是两队石子之和,求最大得分和最小得分

显然,本题是区间dp。

令\(dp[i][j]\)表示\(i\)到\(j\)之间合并石子的最小值(最大值同理),则我们可以很轻松地列出状态转移方程为:
\[ dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+d(i,j)|i\leq k < j) \]
其中\(d(i,j)\)表示\(i\)到\(j\)之间石子的个数

当问题是最小值时,我们就可以用四边形不等式优化了。此时,对于\(dp[i][j]\),我们只需要在区间\([P[x][y-1],P[x+1][y]]\)枚举\(k\)即可,时间复杂度为\(O(n^2)\)

(注意:最大值并不满足单调性,不能用四边形不等式优化)

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
int dp2[maxn][maxn];
int n;
int a[maxn];
int sum[maxn];
int p[maxn][maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i],p[i][i]=i;
    for(int i=n<<1;i>=1;i--)
        for(int j=i+1;j<=n<<1;j++){
            dp[i][j]=0x3f3f3f3f;
            for(int k=p[i][j-1];k<=p[i+1][j];k++){
                if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<dp[i][j]){
                    dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                    p[i][j]=k;
                }else if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]==dp[i][j])
                    p[i][j]=max(p[i][j],k);
            }
        }
    for(int len=2;len<=n;len++){  
        for(int i=1;i<=n*2;i++){  
            int j=i+len-1;
            if(j>2*n) break;
            for(int k=i;k<j;k++){  
                dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);    
            }  
        }  
    }  
    int ans=0x3f3f3f3f;
    int ans2=0;
    for(int i=1;i<=n;i++) ans=min(ans,dp[i][i+n-1]);
    for(int i=1;i<=n;i++) ans2=max(ans2,dp2[i][i+n-1]); 
    printf("%d\n%d\n",ans,ans2);
    return 0;
}
上一篇:【NX二次开发】创建有界平面UF_MODL_create_bplane


下一篇:[atAGC051C]Flipper