记录编号	478225	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	_WA自动机	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2017-12-09 21:31:11	内存使用	0.74 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10;
int minn[maxn][maxn],maxx[maxn][maxn],n,sum[maxn],sz[maxn];
bool vis1[maxn][maxn],vis2[maxn][maxn];
int dfs(int i,int j)
{
    if (vis1[i][j]) return minn[i][j];
    if (i==j) {vis1[i][j]=vis2[i][j]=true;return minn[i][j]=maxx[i][j]=0;}
    int ans=INT_MAX;
    for (int k=i;k<j;++k)
        ans=min(ans,dfs(i,k)+dfs(k+1,j));
    ans+=sum[j]-sum[i-1];
    vis1[i][j]=true;
    return minn[i][j]=ans;
}
int dp(int i,int j)
{
    if (vis2[i][j]) return maxx[i][j];
    if (i==j) {vis2[i][j]=true;return maxx[i][j]=0;}
    int& ans=maxx[i][j];
    for (int k=i;k<j;++k)
        ans=max(ans,dp(i,k)+dp(k+1,j));
    vis2[i][j]=1;
    return ans+=sum[j]-sum[i-1];
}
int main()
{
    freopen("stone2.in","r",stdin);
    freopen("stone2.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        sz[i]=a;
        sum[i]=sum[i-1]+a;
    }
    for (int i=n+1;i<=(n<<1);++i)
        sum[i]=sum[i-1]+sz[i-n];
    int mi=INT_MAX,ma=0;
    for (int i=1;i<=n;++i)
    {
        mi=min(dfs(i,i+n-1),mi);
        ma=max(dp(i,i+n-1),ma);
    }
    printf("%d\n%d",mi,ma);
    return 0;
}