P1880 NOIP 1995石子合并

复习（du） 这道题，发现思想真不错

当时背板子打下来的

要下晚自习了，明天更注释吧

#include<iostream>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int f2[200][200],f1[200][200];
int s[1008],n;
int a[1008];
int ans1,ans2;
int sum(int left,int right)
{
    return s[right]-s[left-1];
}
int main()
{
    memset(f1,-1,sizeof(f1));
    memset(f2,0x3f,sizeof(f2));
    int i,j;
    scanf("%d ",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=a[i]+s[i-1];
        a[i+n]=a[i];
        f1[i][i]=0;
        f2[i][i]=0;
    }
    for(i=n+1;i<=n*2;i++)
    {
    s[i]=a[i]+s[i-1];
    f1[i][i]=0;
    f2[i][i]=0;    
    }
    
    int l,k;
    for(l=2;l<=n;l++)
    for(i=1;i<=2*n-l;i++)
    {
        j=i+l-1;
        for(k=i;k<j;k++)
        {
            f1[i][j]=max(f1[i][k]+f1[k+1][j],f1[i][j]);
            f2[i][j]=min(f2[i][k]+f2[k+1][j],f2[i][j]);
        }
        f1[i][j]+=sum(i,j);
        f2[i][j]+=sum(i,j); 
    }
    ans1=-1;
    ans2=0x3f3f3f3f;
    for(i=1;i<=n;i++)
    {
        ans1=max(ans1,f1[i][i+n-1]);
        ans2=min(ans2,f2[i][i+n-1]);
     } 
     printf("%d\n%d ",ans2,ans1);
     return 0;
}