记录编号	566649	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2021-11-15 20:57:54	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long 
using namespace std;
int nc; 
int n[205];
int f[105][105];
int main()
{
	freopen("shizi.in","r",stdin);
	freopen("shizi.out","w",stdout);
    scanf("%d",&nc);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=nc;i++)
    {
    	scanf("%d",&n[i]);
    	n[i]+=n[i-1];
    	f[i][i]=0;
    }
    for(int l=2;l<=nc;l++)
    {
    	for(int st=1,ed;st+l-1<=nc;st++)
    	{
    		ed=st+l-1;
    		for(int k=st+1;k<=ed;k++)
    		{
    			f[st][ed]=min(f[st][ed],f[st][k-1]+f[k][ed]);
    		}
    		f[st][ed]+=(n[ed]-n[st-1]);
    	}
    }
    printf("%d\n",f[1][nc]);
    return 0;
}