AcWing 282. 石子合并---区间dp
原题链接
简单
作者:
上班摸鱼中
,
2023-03-23 11:05:07
,
所有人可见
,
阅读 92
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int s[N];
int f[N][N];
int n;
int main(){
cin>>n;
//每次合并石头的代价是把从i到j的所有石头加起来
//正好是前缀和!!!!
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];
}
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j= i+len-1;
f[i][j]=1e8; //必须要先给f[i][j]一个非常大的初始值
//才能在后面取最小值的时候取到最小值,否则答案全是0了
for(int k=i;k<j;k++) //k是从i到j依次把石头分成两堆的隔板
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
}
}
cout<<f[1][n]<<endl;
return 0;
}