二维四边形不等式优化DP

前导知识

区间包含的单调性：如果对于i≤i'< j≤j’，有w(i’,j)≤w(i,j’)，那么说明w具有区间包含的单调性。

定义

如果对于任意的a1≤a2<b1≤b2，有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1]，那么m[i,j]满足四边形不等式。

定理

对二维四边形模板方程 F(i,j)=min{F(i,k)+F(k+1,j)}+w(i,j)(i≤k≤j)

且s(i,j)表示F(i,j)取得最优值时对应的k， 称它为f[i,j]的最优决策，有:

定理一：如果上述的w函数同时满足区间包含单调性和四边形不等式性质，那么函数F也满足四边形不等式性质。

定理二：假如F(i,j)满足四边形不等式，那么s(i,j)单调，即s(i-1,j)≤s(i,j)≤s(i,j-1)

证明

以石子合并为例

普通动态转移方程 F(i,j)=min{F(i,k)+F(k+1,j)}+sum[j]-sum[i-1](i≤k≤j)

很明显，对于前缀和sum来说，它既满足区间包含单调性也满足四边形不等式性质

定理一证明

当i+1=j时，F[i,j+1]+F[i+1,j]=F[i,i+2]+F[i+1,i+1]=F[i,i+2]

若F[i,i+2]的最优决策是i+1，则

F[i,i+2]=F[i,i+1]+F[i+2,i+2]+Sum[i,i+2]=Sum[i,i+1]+Sum[i,i+2] ≥Sum[i,i+1]+Sum[i+1,i+2]=F[i,i+1]+F[i+1,i+2]=F[i,j]+F[i+1,j+1]

若F[i,i+2]的最优决策是i，则

F[i,i+2]=F[i,i]+F[i+1,i+2]+Sum[i,i+2]=Sum[i,i+1]+Sum[i,i+2]   ≥Sum[i+1,i+2]+Sum[i,i+1]=F[i+1,i+2]+F[i,i+1]=F[i+1,j+1]+F[i,j]

所以当i+1=j时,F[i,j+1]+F[i+1,j]≥F[i,j]+F[i+1,j+1]

也就是说当i+1=j时，F满足四边形不等式

接下来，用数学归纳法，假设当j-i<k时，四边形不等式对F[i,j]成立。考虑j-i=k的情况，设F[i,j+1]以x为最优决策，F[i,j+1]以y为最优决策。不妨设i+1≤x≤y

根据x和y的最优性，有：

F[i,j+1]+F[i+1,j]=F[i,x]+F[x+1,j+1]+Sum[i,j+1]

       +F[i+1,y]+F[y+1,j]+Sum[i+1,j]……. ①

对于F[i,j]和F[i+1,j+1]，x和y是任意决策(不一定最优)，故：

F[i,j]+F[i+1,j+1]≤F[i,x]+F[x+1,j]+Sum[i,j]

       +F[i+1,y]+F[y+1,j+1]+Sum[i+1,j+1]……②

因为Sum满足四边形不等式 Sum[i,j+1]+Sum[i+1,j]≥Sum[i,j]+Sum[i+1,j+1]

根据归纳假设，有：F[x+1,j+1]+F[y+1,j]≥F[x+1,j]+F[y+1,j+1]

结合这两个不等式，比较①②两式，得到： F[i,j+1]+F[i+1,j]≥F[i,j]+F[i+1,j+1]

证毕

定理二证明

我们记S=s[i,j]，对于任意的i＜k≤S，因为F满足四边形不等式：F[i,S]+F[i+1,k]≥F[i,k]+F[i+1,S]

移项可得：F[i+1,k]-F[i+1,S]≥F[i,k]-F[i,S]

根据S的最优性，有：F[i,k]+F[k+1,j]≥F[i,S]+F[S+1,j]

因此：

  (F[i+1,k]+F[k+1,j]+Sum[i+1][j])-(F[i+1,S]+F[S+1,j]+Sum[i+1][j])

=(F[i+1,k]-F[i+1,S])+(F[k+1,j]-F[S+1,j])≥(F[i,k]-F[i,S])+(F[k+1,j]-F[S+1,j])

=(F[i,k]+F[k+1,j])-(F[i,S]+F[S+1,j])≥0

也就是说对于F[i+1,j],S比任意k≤S更优。所以S[i+1,j]≥S[i,j]

同理S[i,j-1]≤S[i,j]

优化方法

如果f[i,j]满足四边形不等式性质，那么s[i-1,j]≤s[i,j]≤s[i,j-1]

所以我们可以从前面的动态转移中限定后一个状态中的决策

这样我们就可以降低时间复杂度

这是不用四边形不等式的O(N^3)算法

for(int l=2;l<=n;l++)
   for(int i=1;i<=n*2-l+1;i++)
   {
      int j=i+l-1;
      fmin[i][j]=0x7fffffff;
      for(int k=i;k<j;k++)
         fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]);
   }

用了四边形不等式优化，接近O(N^2)

for(int i=(n<<1)-1;i;i--)
    for(int j=i+1;j<=(n<<1);j++)
	{
            int jc=0,tmp=0x3f3f3f3f;
            for(int k=smi[i][j-1];k<=smi[i+1][j];k++)
	    {
                int tt=fmi[i][k]+fmi[k+1][j]+(sum[j]-sum[i-1]);
                if(tt<tmp)
                {
                      tmp=tt;
                      jc=k;
		}
	    }
            smi[i][j]=jc;fmi[i][j]=tmp;
         }