石子合并
题面
设有 N 堆石子排成一排，其编号为 1,2,3,…,N。
每堆石子有一定的质量 \(a_i\) ，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
\(1 \le N \le 300\)
\(0 \le a_i \le 1000\)
题解
这是区间 dp 板子，因为合并时只能合并相邻的两堆石子，所以每堆石子都可以用一个闭区间 \([l,r]\) 表示，而这个闭区间可以从 \([l,k]\) 和 \([k + 1, r]\) 两个子区间转移过来，所以我们可以将区间长度 \(len\) 作为 “阶段” ，左端点和右端点就是状态，中间的 \(k\) 就是 “决策”
设 \(f(l,r)\) 为将 \([l,r]\) 合并为一堆石子的最小代价
转移 \(f(l,r) = min \{f(l,k) + f(k + 1, r)\} + sum(l,r)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;typedef long long ll;const int N = 310;int n;
int a[N], sum[N], f[N][N];int main () {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];sum[i] = a[i] + sum[i - 1];}memset (f, 0x3f, sizeof f);for (int i = 1; i <= n; i++) {f[i][i] = 0;}for (int len = 2; len <= n; len ++) {for (int l = 1; l + len - 1 <= n; l ++) {int r = l + len - 1;for (int k = l; k < r; k ++) {f[l][r] = min (f[l][r], f[l][k] + f[k + 1][r]);}f[l][r] += sum[r] - sum[l - 1];}}cout << f[1][n] << endl;return 0;
}