DP 总结
DP
即动态规划（Dynamic Programming），是数学中比较冷门的学科，通过分解成若干个子问题合并而成。主要有：
- 背包问题
- 区间 DP
- 状态压缩 DP
DP 特征：无后效性，最优子结构，子问题重叠。
背包问题：
0-1 背包
例题：luogu P1048 采药
- 题意：
给出物品的重量 \(w_i\) 和价值 \(v_i\)，每个物品只能选一次，问最大价值。
- 思路：
设方程 \(f_{i,j}\) 为取前 \(i\) 个物品，容量为 \(j\) 时的最大价值。
则 \(f_{i,j}=\max\{f_{i-1,j}, f_{i-1,j-w_i}+v_i\}\)。什么意思呢：如果当前物品不选，那么直接从 \(i-1\) 转移过来（\(f_{i-1,j}\)）。如果当前选，那么这个除了物品之外的总容量为 \(j - w_i\)，呢我们直接调用 \(f_{i-1,j-w_i}\) 加上选的价值即可。
for (int i = 1; i <= m; i++) {
for (int j = t; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + e[i]);
}
}
多重背包
例题：luogu P1616 疯狂的采药
- 题意：
给出物品的重量 \(w_i\) 和价值 \(v_i\)，每个物品可以选无限次，问最大价值。
- 思路：
考虑 \(O(n^3)\) 暴力，枚举 \(k\) 为选择物品的数量（\(k\le \dfrac{w_i}{j}\)），所以转移方程为：
\(f_{i,j}=\max\{f_{i-1,j\times k}+v_i\times k\}\)。
怎么优化呢？
发现对于 \(f_{i,j-w_i}\) 由 \(f_{i,j-w_i\times k}\) 转移过来，所以我们就不用枚举 \(k\) 了，即 \(f_{i,j}\) 从 \(f_{i,j-w_i}\) 转移过来。
然后可以滚动数组优化掉第一维：
for (long long i = 1; i <= m; i++) {
for (long long j = e[i]; j <= t; j++) {
dp[j] = max(dp[j], dp[j - e[i]] + w[i]);
}
}
完全背包
其实就朴素的多重背包。
转移方程：\(f_{i,j}=\max\limits_{k=0}^nk_i\{f_{i-1,j-w_i \times k}+v_i\times k\}\)
混合背包
就是上面三种背包的结合。判断一下做出相应匹配背包即可。
分组背包
例题：luogu P1757 通天之分组背包
- 题意：
有 \(n\) 件物品和一个大小为 \(m\) 的背包，第 \(i\) 个物品的价值为 \(w_i\)，体积为 \(v_i\)每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。
- 思路：
就是对于每组求一次 0-1 背包即可。
for (int k = 1; k <= ts; k++) {
for (int i = m; i >= 0; i--) {
for (int j = 1; j <= cnt[k]; j++) {
if (i >= w[t[k][j]]) {
dp[i] = max(dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]);
}
}
}
}
区间 DP
顾名思义，就是在区间上进行 DP。
DP 顺序为从区间长度小的转移到大的上来。所以我们可以枚举一个断点 \(k\)，然后枚举两个端点 \(i,j\)，\(j\) 为 \(i+k-1\)。然后我们就在这个区间 \([i,j]\) 做操作。
例题：luogu P1063 能量项链
- 题意：
有一个环，每次可以选择相邻两个合并，如果前一颗能量珠的头标记为 \(m\)，尾标记为 \(r\)，后一颗能量珠的头标记为 \(r\)，尾标记为 \(n\)，则聚合后释放的能量为 \(m\times r\times n\)，头标为 \(m\)，尾标为 \(n\)。求最大代价。
- 思路：
显然破环为链。
显然 \(f_{i,j}=\max\{f_{i,j}, f{i,k}+f_{k+1,j}+a_i \times a_{k+1} \times a_{j+1}\}\)。
就是由区间 \([i,k]\) 和区间 \([k+1,j]\) 的最大值相加得到的。然后还要加上珠子合并所产生的代价。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 100;
int n, a[MAXN], dp[MAXN][MAXN], ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
for (int l = 2; l <= n; l++) {
for (int i = 1; i + l - 1 <= n << 1; i++) {
int j = i + l - 1;
for (int k = i; k < j; k++) {
ans = max(ans, dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]));
}
}
}
cout << ans;
return 0;
}