有人问我这题怎么做?

其实和 #P1775. 石子合并（弱化版）只有一点点区别

可以注意到 #P1775. 石子合并（弱化版）里的石子是一条链

而这题里的石子是一个环

所以只要把环变成链就好了

做法：把数组复制一次即可

#include<iostream>
#include<climits>
using namespace std;
const int maxn=1E3+10;
int n, m[maxn], dp[maxn][maxn], dp2[maxn][maxn], pre_sum[maxn], max_ans=INT_MIN, min_ans=INT_MAX;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
		pre_sum[i]=pre_sum[i-1]+m[i];//前缀和加速区间代价计算 
	}
	for(int i=n+1,j=1;j<=n;i++,j++){
		m[i]=m[j];
		pre_sum[i]=pre_sum[i-1]+m[i]; 
	}
	/*//写法1：l、r端点反向扩展实现了区间长度变大的扩展,不动脑直接2n区间处理
	for(int l=2*n;l>=1;l--){//for(int l=2*n-1;l>=1;l--)
		dp[l][l]=0;dp2[l][l]=0;
		for(int r=l+1;r<=2*n;r++){//for(int r=l+1;r<2*n && r-l<=n-1;r++)
			dp[l][r]=INT_MAX;dp2[l][r]=INT_MIN;
			for(int k=l;k<r;k++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+pre_sum[r]-pre_sum[l-1]);
				dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]+pre_sum[r]-pre_sum[l-1]);
			}
		}
	}*/
	/*//写法2：上面的写法改进一点
	//如果考虑极端区间是[1,n]->[n,2*n-1] ，2*n后或者长度>=n的区间根本没必要
	for(int l=2*n-1;l>=1;l--){
		dp[l][l]=0;dp2[l][l]=0;
		for(int r=l+1;r<2*n && r-l<=n-1;r++){
			dp[l][r]=INT_MAX;dp2[l][r]=INT_MIN;
			for(int k=l;k<r;k++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+pre_sum[r]-pre_sum[l-1]);
				dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]+pre_sum[r]-pre_sum[l-1]);
			}
		}
	}*/
	//写法3：直接循环变量枚举区间长度len
	for(int i=1;i<=2*n-1;i++)	dp[i][i]=dp2[i][i]=0;//len==1没有合并代价
	for(int len=2;len<=n;len++){
		for(int l=1,r=1+len-1; r<2*n; l++,r++){
			dp[l][r]=INT_MAX;dp2[l][r]=INT_MIN;
			for(int k=l;k<r;k++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+pre_sum[r]-pre_sum[l-1]);
				dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]+pre_sum[r]-pre_sum[l-1]);
			}
		}
	}

	for(int l=1;l<=n;l++){
		min_ans=min(min_ans, dp[l][l+n-1]);
		max_ans=max(max_ans, dp2[l][l+n-1]);
	}
	cout<<min_ans<<endl<<max_ans;
	return 0;
}

纯大力飞砖版，感谢C24liukaiwen提供的记忆化搜索

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int n,a[maxn],dpmin[maxn][maxn],dpmax[maxn][maxn],str[maxn],pp[maxn];
int dfsmin(int l,int r){
	if(l==r)return 0;
	if(dpmin[l][r]!=INT_MAX)return dpmin[l][r];
	for(int i=l;i<r;i++){
		dpmin[l][r]=min(dpmin[l][r],dfsmin(l,i)+dfsmin(i+1,r)+a[r]-a[l-1]);
	}return dpmin[l][r];
}
int dfsmax(int l,int r){
	if(l==r)return 0;
	if(dpmax[l][r]!=0)return dpmax[l][r];
	for(int i=l;i<r;i++){
		dpmax[l][r]=max(dpmax[l][r],dfsmax(l,i)+dfsmax(i+1,r)+a[r]-a[l-1]);
	}return dpmax[l][r];
}
int main(){
	int ansmin=INT_MAX,ansmax=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>str[i];
	for(int i=1;i<=n;i++){
		a[0]=0;
		for(int j=i,k=1;k<=n;k++,j++){
			if(j>n)j-=n;
			a[k]=str[j];
			a[k]+=a[k-1];
		}
		for(int i=0;i<maxn;i++){
			for(int j=0;j<maxn;j++){
				dpmin[i][j]=INT_MAX;
			}
		}
		for(int i=0;i<maxn;i++){
			for(int j=0;j<maxn;j++){
				dpmax[i][j]=0;
			}
		}
		ansmin=min(ansmin,dfsmin(1,n));
		ansmax=max(ansmax,dfsmax(1,n));
	}
	cout<<ansmin<<endl<<ansmax;
	return 0;
}

正常的记忆化搜索写法（正解）

#include<bits/stdc++.h>
using namespace std;
const int maxn=410;
int n,a[maxn],dpmin[maxn][maxn],dpmax[maxn][maxn];
inline int dfsmin(int l,int r){
    if(l==r) return 0;
    if(dpmin[l][r]!=INT_MAX) return dpmin[l][r];
    for(int i=l;i<r;i++){
        dpmin[l][r]=min(dpmin[l][r],dfsmin(l,i)+dfsmin(i+1,r)+a[r]-a[l-1]);
    }
    return dpmin[l][r];
}
inline int dfsmax(int l,int r){
    if(l==r) return 0;
    if(dpmax[l][r]!=0) return dpmax[l][r];
    for(int i=l;i<r;i++){
        dpmax[l][r]=max(dpmax[l][r],dfsmax(l,i)+dfsmax(i+1,r)+a[r]-a[l-1]);
    }
    return dpmax[l][r];
}
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++)a[i]+=a[i-1];
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            dpmin[i][j]=INT_MAX;
            dpmax[i][j]=0;
        }
    }
    int ansmin=INT_MAX,ansmax=0;
    for(int i=1;i<=n;i++){
        ansmin=min(ansmin,dfsmin(i,i+n-1));
        ansmax=max(ansmax,dfsmax(i,i+n-1));
    }
    cout<<ansmin<<endl<<ansmax;
    return 0;
}

四边形不等式$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; 
}