AcWing 282. 石子合并
原题链接
简单
作者:
chenjiaqiy
,
2023-11-21 11:07:50
,
所有人可见
,
阅读 46
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 310;
int s[N];
int f[N][N];
int main ()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
//如果len == 1,表示一堆,不需要合并,代价为0;
for (int len = 2; len <= n; len ++ )//按照长度从小到大枚举所有状态
for (int i = 1; i + len - 1 <= n; i ++ ) //枚举所有起点
{
int l = i, r = i + len - 1; //表示该区间的起点和终点
f[l][r] = 1e8;
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]);
}
cout << f[1][n] << endl;
return 0;
}