AcWing 282. 石子合并
原题链接
简单
作者:
我要出去乱说
,
2021-01-28 14:26:51
,
所有人可见
,
阅读 305
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310, INF = 1e9;
int n;
int s[N];
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> s[i];
for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1]; //计算前缀和
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] = INF; //要求最小值,先初始化为无穷大
for (int k = l; k < r; k ++ )
//f[l][k]+f[k+1][r]表示起点为l终点为k的最小代价+起点为k+1终点为j的最小代价
//即除了最后一步之外的总最小代价。s[r]-s[l-1]为最后一步的代价
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n] << endl; //起点为1长度为n的集合
return 0;
}