https://www.luogu.com.cn/problem/P1880

题意：在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

将原有长度复制一份接在后面，然后跑 [1,n] 就可以保证取到所有起点的区间，这样仍可取到环形结构中的所有情况，是等价的。

本题的转移方程： $d[i][j]=max(d[i][k] + d[k+1][j]) + c[i][j]$

max 换成 min 就是最小值的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int MAX=100+5;
int n,a[MAX*2],c[MAX*2][MAX*2],sum[MAX*2],d[MAX*2][MAX*2],m[MAX*2][MAX*2];
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,0,n){
		sf(a[i]);
		a[i+n]=a[i];
	} 
	sum[0]=a[0];
	fi(i,1,n*2){
		sum[i]=sum[i-1]+a[i];
	}	
	fi(i,0,n*2)
		fi(j,i,n*2){
			c[i][j]=sum[j];
			if(i-1>=0)c[i][j]-=sum[i-1];
			m[i][j]=INF;
		}
	fi(i,0,n*2) m[i][i]=0;
	fi(l,2,n*2)
		fi(i,0,n*2-l+1){
			int j=i+l-1;
			fi(k,i,j){
				d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]+c[i][j]);
				m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+c[i][j]);
			}
		}	
	int _max=0,_min=INF;	
	fi(i,0,n){
		_max=max(_max,d[i][i+n-1]);
		_min=min(_min,m[i][i+n-1]);
	}
	printf("%d\n%d",_min,_max);
	return 0;
}