石子合并合集(区间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