难度： 绿

算符标签： 区间 dp，四边形不等式优化（可选）

记 $f[j][i]$ 为以 $j$ 开始的 $i$ 个数的（最大/最小）操作费用，$s[i]$ 为前缀和。则有：

$$f[j][i]=max/min(f[j][i],f[j][k]+f[j+k][i-k]+s[j+i-1]-s[j-1]) $$

几个注意事项：

1. $d[i][1]=0$

2. 输出最大值时要除 $2$ （我也不知道为什么）

实现见代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,d[444]={},f[444][444]={},s[444]={},ans=1e9;
int main(){
	memset(f,0x3f3f3f,sizeof(f));
	scanf("%d",&n);
	m=n,n=2*n-1;
	for(int i=1;i<=m;i++) scanf("%d",&d[i]),s[i]=s[i-1]+d[i];
	for(int i=m+1;i<=n;i++) d[i]=d[i-m],s[i]=s[i-1]+d[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-i+1;j++){
			if(i==1) f[j][i]=0;
			else{
				for(int k=1;k<=i;k++){
					f[j][i]=min(f[j][i],f[j][k]+f[j+k][i-k]+s[j+i-1]-s[j-1]);
				}
			}
		}
	}
	for(int i=1;i<=m;i++) ans=min(ans,f[i][m]);
	printf("%d\n",ans);
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-i+1;j++){
			if(i==1) f[j][i]=0;
			else{
				for(int k=1;k<=i;k++){
					f[j][i]=max(f[j][i],f[j][k]+f[j+k][i-k]+s[j+i-1]-s[j-1]);
				}
			}
		}
	}
	for(int i=1;i<=m;i++) ans=max(ans,f[i][m]);
	printf("%d\n",ans/2);
	return 0;
}