四边形不等式$O(n^3)$优化至$O(n^2)$

改前代码（不会就先不要看此题解）

#include<bits/stdc++.h>
using namespace std;
int firs[415],a[415];
int dp_min[415][415];
int dp_max[415][415];
int n;
void fir(){
   for(int i=1;i<=2*n;i++){
      firs[i]=a[i];
      firs[i]+=firs[i-1];
   }
}
signed main(){
   memset(dp_min,0x3f,sizeof(dp_min));
   memset(dp_max,-0x3f,sizeof(dp_max));
   
   cin>>n;
   for(int i=1;i<=n;i++){
      cin>>a[i];
      a[i+n]=a[i];
      dp_min[i][i]=dp_min[i+n][i+n]=0;
      dp_max[i][i]=dp_max[i+n][i+n]=0;
      
   }
   fir();
   int min_num=INT_MAX,max_num=INT_MIN;
   for(int i=2;i<=n;i++){
      for(int s=1;s+i-1<=2*n;s++){
         int j=s+i-1;
         for(int k=s;k<j;k++){
            dp_max[s][j]=max(dp_max[s][j],dp_max[s][k]+dp_max[k+1][j]+firs[j]-firs[s-1]);
            dp_min[s][j]=min(dp_min[s][j],dp_min[s][k]+dp_min[k+1][j]+firs[j]-firs[s-1]);
         }
      }
      

   }
   for(int i=1;i<=n;i++){
      max_num=max(dp_max[i][i+n-1],max_num);
      min_num=min(min_num,dp_min[i][i+n-1]);
   } 
   cout<<min_num<<endl<<max_num;




   return 0; 
}

前言-四边形不等式

1. 什么是四边形不等式？

四边形不等式（Quadrangle Inequality）是一种数学工具，用来优化动态规划问题中的区间合并计算。

例子

• 你有一排石子，每个石子有一个数字（比如重量或分数）。
• 每次你可以合并相邻的两堆石子，合并的得分是这两堆石子的数字之和。
• 你的目标是找到合并所有石子的最小总得分或最大总得分。

四边形不等式就是帮你快速找到最优合并顺序的捷径

---

2. 为什么需要四边形不等式？

如果没有四边形不等式，计算所有可能的合并顺序会很慢，比如：

• 如果有 4 堆石子，合并顺序有 5 种可能。
• 如果有 10 堆石子，合并顺序就有 4862 种可能！

四边形不等式告诉我们：

最优合并点（在哪里分割）有序移动。

这样我们就不用检查所有可能的分割点

---

定义

$$\forall a \leq b \leq c \leq d, \quad w(a,d) + w(b,c) \geq w(a,c) + w(b,d) $$

单调性条件

$$\forall a \leq b \leq c \leq d, \quad w(b,c) \leq w(a,d) $$

决策单调性优化

$$K[i][j-1] \leq K[i][j] \leq K[i+1][j]$$

改后代码

#include<bits/stdc++.h>
using namespace std;
int firs[415],a[415];
int dp_min[415][415], s_min[415][415];
int dp_max[415][415], s_max[415][415];
int n;

void fir(){
   for(int i=1;i<=2*n;i++){
      firs[i]=a[i];
      firs[i]+=firs[i-1];
   }
}

signed main(){
   memset(dp_min,0x3f,sizeof(dp_min));
   memset(dp_max,-0x3f,sizeof(dp_max));
   
   cin>>n;
   for(int i=1;i<=n;i++){
      cin>>a[i];
      a[i+n]=a[i];
      dp_min[i][i]=dp_min[i+n][i+n]=0;
      dp_max[i][i]=dp_max[i+n][i+n]=0;
      s_min[i][i]=s_max[i][i]=i;
      s_min[i+n][i+n]=s_max[i+n][i+n]=i+n;
   }
   fir();
   int min_num=INT_MAX,max_num=INT_MIN;
   
   for(int len=2;len<=n;len++){
      for(int s=1;s+len-1<=2*n;s++){
         int j=s+len-1;
         int l=s_min[s][j-1],r=s_min[s+1][j];
         for(int k=l;k<=r&&k<j;k++){
            if(dp_min[s][j]>dp_min[s][k]+dp_min[k+1][j]+firs[j]-firs[s-1]){
               dp_min[s][j]=dp_min[s][k]+dp_min[k+1][j]+firs[j]-firs[s-1];
               s_min[s][j]=k;
            }
         }
         for (int k=s;k<j;k++) {
            if (dp_max[s][j]<dp_max[s][k]+dp_max[k+1][j]+firs[j]-firs[s-1]){
               dp_max[s][j]=dp_max[s][k]+dp_max[k+1][j]+firs[j]-firs[s-1];
               s_max[s][j]=k;
            }
         }
      }
   }
   
   for(int i=1;i<=n;i++){
      max_num=max(dp_max[i][i+n-1],max_num);
      min_num=min(min_num,dp_min[i][i+n-1]);
   } 
   cout<<min_num<<endl<<max_num;
   return 0; 
}