石子合并合集(区间DP)


1.

https://www.acwing.com/problem/content/description/284/

题目大意:

N 堆石子排成 一排 ,编号为 1, 2, 3,..., N。每堆石子有一定的质量,用一个整数来表述,现要将这 N 堆石子合并成为一堆,每次只能合并 相邻 的两堆,合并的代价为这两堆的质量之和,合并后这两堆石子相邻的石子将和新堆相邻,找出最合理的方式,使总代价最小,输出最小代价

思路:

区间 DP,每次合并的结果可以由之前那两堆的石子转移过来,于是我们可以想到用 长度 作为最外层循环,再循环 **起点 i ** ,可以知道 **终点 j **, 再找 **中间节点 k **,得到转移方程 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + 代价), 代价 就是整个区间石子质量的和。

代码:

#include 
using namespace std;
const int MAX = 400;
const int INF = 1e9;
int n, dp[MAX][MAX];
vector  num(MAX), s(MAX);
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		scanf("%d", &num[i]);
		s[i] = s[i - 1] + num[i];  //求质量前缀和
	}
	for (int len = 2; len <= n; len++)
		for (int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			dp[i][j] = INF;  //初始化为极大的值
			for (int k = i; k < j; k++)
				dp[i][j] = min(dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1], dp[i][j]);
		}
	cout << dp[1][n] << "\n";
	return 0;
}

未完待续...
2.

https://www.luogu.com.cn/problem/P1880

3.

https://www.luogu.com.cn/problem/P5569

DP