环形的处理P1880 [NOI1995]石子合并

Description

在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成 1堆的最小得分和最大得分。

数据的第 1 行是正整数 N，表示有N堆石子。
第 2 行有 N个整数，第 i 个整数 \(a_i\)表示第 i 堆石子的个数。
输出共 2 行，第 1 行为最小得分，第 2行为最大得分。

Input

4
4 5 9 4

Output

43
54

Analysis

决策容易分析，最优子结构有两部分
断环为链：将长度为n的链复制一份接在后面，环的情况就是长度为2n的链中任意连续的长度为n的链。

Code

我的写法

#include
using namespace std;
int s[101],a[100],xp[100][100],dp[100][100];
int main(){
    int n,i,j,maxi=0,mini=200000;scanf("%d",&n);
    for(i=0;i

#include
using namespace std;
int n,l,anss,ansb,a[110],sum[210],dp[210][210],dpbig[210][210];
int main(){
	memset(dp,0x3f,sizeof(dp)); anss=dp[0][0];
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i]; a[0]=a[n];
	for (int i=1;i<=2*n;i++){
		sum[i]=sum[i-1]+a[i%n];
		dp[i][i]=0;
	}
	for (int len=2;len<=n;len++){
		for (int r=len;r<=2*n;r++){
			l=r-len+1;
			for (int j=l;j