石子合并

断环为链。

环形的最优合并方式，一定可以展开成长为n的链来处理。

怎样才是最优的合并方式？

n<=100。

枚举处理。

#include<bits/stdc++.h>
using namespace std;

signed main()
{
    int n; 
    cin>>n;
    vector<int>a(n+n+n+1),sum=a;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }

    for(int i=1;i<=3*n;i++)
    sum[i]=sum[i-1]+a[i];

    vector<vector<int>>f1(3*n+10,vector<int>(3*n+10,1e9)),f2(3*n+10,vector<int>(3*n+10,0));

    for(int i=1;i<=2*n;i++)
    f1[i][i]=0;

    for(int i=1;i<=2*n;i++)
    f1[i][i+1]=a[i]+a[i+1],
    f2[i][i+1]=a[i]+a[i+1];

    for(int len=3;len<=2*n;len++){
        for(int l=1;l+len-1<=2*n;l++){
            int r=l+len-1;
            for(int i=l;i<r;i++){
                f1[l][r]=min(f1[l][i]+f1[i+1][r]+sum[i]-sum[l-1]+sum[r]-sum[i],f1[l][r]);
                f2[l][r]=max(f2[l][i]+f2[i+1][r]+sum[i]-sum[l-1]+sum[r]-sum[i],f2[l][r]);
            }

        }
    }
    int ans1=f1[1][n],ans2=f2[1][n];
    for(int i=2;i<=n;i++)
    ans1=min(f1[i][i+n-1],ans1),
    ans2=max(f2[i][i+n-1],ans2);

    cout<<ans1<<endl<<ans2;

    
}

25/2/15