前言
AcWing算法提高课内容，本文讲解 动态规划
本篇包括以下题目：
⭐️ AcWing 1068. 环形石子合并
⭐️ AcWing 320. 能量项链
⭐️ AcWing 479. 加分二叉树
⭐️ AcWing 1069. 凸多边形的划分
写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵
本文需要先自修基础：区间DP
环形石子合并
题目要求
题目描述：
输入格式：
第一行包含整数 n ，表示共有 n 堆石子。
第二行包含 n 个整数，分别表示每堆石子的数量。
输出格式：
输出共两行：
第一行为合并得分总和最小值，
第二行为合并得分总和最大值。
数据范围：
1≤n≤200
输入样例：
4 4 5 9 4
输出样例：
43 54
思路分析
环形的问题我们都可以变环为线，即我们开两倍的大小，然后以n为长度进行枚举即可，下面给一个示例图：
这样，我们直接对展开的直线以长度为 6 进行遍历，和直接枚举一个环的效果是一致的，为了更快的求出一段区间的和，可以使用前缀和的思维进行优化，前缀和讲解见博客：前缀和算法
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 410; int f[N][N], g[N][N]; int w[N], s[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i]; for (int i = 1; i <= 2 * n; i ++ ) s[i] = s[i - 1] + w[i]; memset(g, 0x3f, sizeof g); for (int i = 1; i <= 2 * n; i ++ ) g[i][i] = 0; for (int len = 2; len <= n; len ++ ) for (int l = 1; l + len - 1 <= 2 * n; l ++ ) { int r = l + len - 1; for (int k = l; k < r; k ++ ) { f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]); } } int maxv = 0, minv = 0x3f3f3f3f; for (int i = 1; i <= n; i ++ ) { maxv = max(maxv, f[i][i + n - 1]); minv = min(minv, g[i][i + n - 1]); } cout << minv << endl << maxv; return 0; }
能量项链
题目要求
题目描述：
输入格式：
输出格式：
输出只有一行，是一个正整数E,为一个最优聚合顺序所释放的总能量。
数据范围：
输入样例：
4 2 3 5 10
输出样例：
710
思路分析
是 环形石子合并 的一个升级，思路还是一致的，对应到代码上有一些微处理，比如合并的长度最少是3,区间dp间断点的枚举必须从 l + 1 进行枚举
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 210; int f[N][N]; int w[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i]; for (int len = 3; len <= n + 1; len ++ ) for (int l = 1; l + len - 1 <= 2 * n; l ++ ) { int r = l + len - 1; for (int k = l + 1; k < r; k ++ ) f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]); } int maxv = 0; for (int i = 1; i <= n; i ++ ) maxv = max(maxv, f[i][i + n]); cout << maxv << endl; return 0; }
