[51nod - 1021] 石子归并

发表于 | 更新于 | 分类于 ， ，
本文字数： 11k

链接

\(\text{51nod - 1021}\)

题意

  有\(N\)堆石子排成一排，其中第\(i\)堆石子的质量为\(A_i\)，每次都可以选择其中相邻的两堆石子合并成一堆，形成的新石子堆的重量以及消耗的体力都是两堆石子的重量之和。求把全部\(N\)堆石子合成一堆最少需要消耗多少体力。\(1\leq N\leq 300\)。

分析

  这是一个区间\(dp\)入门题目。

  若最初的第\(l\)堆石子和第\(r\)堆石子被合并成一堆，则说明\(l\)~\(r\)之间的每堆石子也已经被合并，这样\(l\)和\(r\)才有可能相邻。因此，在任意时刻，任意一堆石子均可以用一个闭区间\([l,\ r]\)来描述，表示这堆石子是由最初的第\(l\)~\(r\)堆石子合并而成的，其重量为\(\sum_{i=l}^r A_i\)。另外一定存在一个整数\(k(l\leq k<r)\)，在这堆石子形成之前，现有第\(l\)~\(k\)堆石子（闭区间\([l,\ r]\)）被合并成一堆，第\(k+1\)~\(r\)堆石子（闭区间\([k+1,\ r]\)）被合并成一堆，然后这两堆石子才合并成\([l,\ r]\)。

  对应到动态规划中，就意味着两个长度较小的区间上的信息向一个更长的区间发生了转移，划分点\(k\)就是转移的决策，自然地，应该把区间\(len\)作为\(DP\)的阶段，区间长度可以由左右端点表示出，我们可以使用左右端点表示\(DP\)的状态。

  \(dp[l,\ r]\)表示把最初的第\(l\)堆到第\(r\)堆合并到一堆，需要消耗的最少体力。状态转移方程如下：\[dp[l,\ r]=\displaystyle \min_{l\leq k<r}\{dp[l,\ k]+dp[k+1,\ r]\}+\sum_{i=l}^rA_i\]

  \(dp[l][l]=A_l\)，其余为\(\infty\)，最终结果为\(dp[1,\ N]\)，对于\(\sum_{i=l}^rA_i\)可用前缀和计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int read() {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

int n, m, dp[305][305], A[450];

int main() {
	cin >> n;
	int x;
	memset(dp, INF, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		cin >> x;
		A[i] = A[i - 1] + x;
		dp[i][i] = 0;
	}
	for (int len = 1; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			for (int k = l; k < r; k++)
				dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + A[r] - A[l - 1]);
		}
	}
	cout << dp[1][n] << endl;
}