AcWing 282. 石子合并
原题链接
简单
作者:
最后五分钟
,
2024-03-29 15:16:13
,
所有人可见
,
阅读 4
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=310;
typedef pair<int,int> PII;
int f[N][N];
int w[N];
int s[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n;i++)s[i]=s[i-1]+w[i];
memset(f,0x3f,sizeof f);
for(int len=1;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
if(l==r)f[l][r]=0;
else
{
for(int k=l;k<r;k++)
f[l][r]=min(f[l][r],s[r]-s[l-1]+f[l][k]+f[k+1][r]);
}
}
cout<<f[1][n]<<endl;
return 0;
}