如果dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i][j]);且满足dp[a][c]+dp[b][d]<=dp[a][d]+dp[c][d](a<b<=c<d);

那么dp具有四边形不等式性质

另外如果可以证明w[i][j]满足单调性和四边形不等式性质，那么dp也具有四边形不等式性质

单调性：w[i][j]<=w[i][j+1]<=w[i+1][j+1]

 

http://www.51nod.com/Challenge/Problem.html#problemId=1022

 

#include
     
      #define fi first#define se second#define INF 0x3f3f3f3f#define LNF 0x3f3f3f3f3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))const double pi=4.0*atan(1.0);const double e=exp(1.0);const int maxn=1e6+8;typedef long long LL;typedef unsigned long long ULL;//typedef pair
      
        P;const LL mod=1e9+7;const ULL base=1e7+7;using namespace std;LL dp[2008][2008];LL s[2008][2008];LL a[2008];int main(){    int n;    int x;    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%lld",&a[i]);        a[i+n]=a[i];    }    n*=2;    for(int i=1;i<=n;i++){        a[i]+=a[i-1];    }    memset(dp,LNF,sizeof(dp));    for(int i=1;i<=n;i++){        s[i][i]=i;        dp[i][i]=0;    }    for(int i=n;i>=1;i--){        for(int j=i+1;j<=n;j++){            for(int k=s[i][j-1];k<=s[i+1][j];k++){                if(dp[i][j]>dp[i][k]+dp[k+1][j]+a[j]-a[i-1]){                    dp[i][j]=dp[i][k]+dp[k+1][j]+a[j]-a[i-1];                    s[i][j]=k;                }            }        }    }    n/=2;    LL ans=LNF;    for(int i=1;i<=n;i++){        ans=min(ans,dp[i][i+n-1]);    }    printf("%lld\n",ans);}