1.3 区间DP
f(i,j)
:将第i
堆到第j
堆石子合并的最小代价,
划分(i,j)
,则有k=(j-i)
数量不重要个区间,枚举这k个区间,
看哪个区间相结合可以使代价最低。
#include <iostream>
using namespace std;
const int n = 310;
int f[n][n];
int a[n];
int N;
int main()
{
cin >> N;
// 前缀和
for (int i = 1; i <= N; i++)
cin >> a[i], a[i] += a[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++) // (l,k)的代价+(k+1,r)的代价+合并两个区间的代价
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
}
}
cout << f[1][N];
return 0;
}