1068. 环形石子合并

解题报告：之前做过线形的石子合并，现在做这题看了y总的思路，可以通过扩增一倍的数组，枚举长度为n的合并值取最大值和最小值就行啦。

#include<iostream>
#include<cstring>
using namespace std;
const   int N=410;
const   int INF=0x3f3f3f3f;
int w[N],f[N][N],g[N][N];
int s[N];
int main()
{
   
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
   
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int i=1;i<=2*n;i++)
    s[i]=s[i-1]+w[i];
    memset(g,0x3f,sizeof g);
    memset(f,-0x3f,sizeof f);
    for(int len=1;len<=n;len++)
    for(int l=1;l+len-1<=2*n;l++)
    {
   
        int r=l+len-1;
        if(l==r)    f[l][r]=g[l][r]=0;
        else
        {
   
        for(int k=l;k<r;k++)
        {
   
        f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        g[l][r]=min(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
        }
        }
    }
    int minv=INF,maxv=-INF;
    for(int i=1;i<=n;i++)
    {
   
        minv=min(minv,g[i][i+n-1]);
        maxv=max(maxv,f[i][i+n-1]);
    }
    cout<<minv<<endl;
    cout<<maxv<<endl;
    return 0;
    
}