AcWing 282. 石子合并
原题链接
简单
作者:
走不到也得走
,
2020-02-04 16:37:26
,
所有人可见
,
阅读 910
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int a[N],f[N][N];
int s[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);
s[i]=a[i];
}
for(int i=1;i<=n;i++)s[i]+=s[i-1];
for(int len=1;len<=n-1;len++)//i从1开始,所以小于n-1
{
for(int i=1;i+len<=n;i++)
{
int l=i,r=i+len;
f[l][r]=1e9;
for(int k=l;k<r;k++)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
printf("%d",f[1][n]);
return 0;
}