[笔记] 四边形不等式

 

形如f[i][j]=opt{f[i][k]+f[k+1][j]+w(i,j)}的转移方程，有可能使用四边形不等式优化转移。

这是区间DP枚举断点转移的形式之一，本身要枚举三层：长度，左端点，断点，复杂度O(n^3)

借助四边形不等式，可以把内层枚举断点做到均摊O(1)，从而实现O(n^2)的转移。

 

具体要求，设a<b<=c<d，如果转移代价w满足w(a,d)+w(b,c)<=w(a,c)+w(b,d)，那么可以使用四边形不等式优化转移。

记tran[i][j]数组，代表转移到[i,j]区间时所对应的转移点（断点），那么内层循环可以写成

for(int k=tran[i][j-1];k<=tran[i+1][j];k++)

我们以长度为阶段进行转移，所以长度为len-1的tran数组已经计算过了

 

难点在于发现这一特殊的单调性，虽然优化效果非常明显，但是使用范围比较窄。

四边形不等式成立，当且仅当w(i,j)+w(i+1,j+1)<=w(i,j+1)+w(i+1,j)

例：石子合并中关于min的转移优化：

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int MAXN=256;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}

int n,sum[MAXN],val[MAXN];
int g[MAXN][MAXN],trg[MAXN][MAXN];

int main(){
  n=rd();
  memset(g,0x3f,sizeof(g));
  for(int i=1;i<=n;i++){
    g[i+n][i+n]=g[i][i]=0;
    val[i]=val[i+n]=rd();
  }
  for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+val[i];
  for(int i=1;i<=2*n;i++) trg[i][i]=i;
  for(int len=1;len<=n-1;len++){
    for(int i=1;i+len<=2*n;i++){
      int j=i+len;
      for(int k=trg[i][j-1];k<=trg[i+1][j];k++){
        if(g[i][k]+g[k+1][j]+sum[j]-sum[i-1]<g[i][j]){
          g[i][j]=g[i][k]+g[k+1][j]+sum[j]-sum[i-1];
          trg[i][j]=k;
        }
      }
    }
  }
  int mnans=1<<30;
  for(int i=1;i<=n;i++) mnans=min(mnans,g[i][i+n-1]);
  cout<<mnans;
  return 0;
}