动态规划进阶 学习笔记
Yoimiya_miii
·
·
个人记录
贴一篇很好的解题技巧分享博客：https://www.cnblogs.com/C202044zxy/p/15126199.html
0.DP 概述
动态规划具体是什么不多赘述。
面对一道动态规划的问题，我们要考虑的无非以下几点：转移对象，转移顺序，转移边界 \dots
其中有很多设计状态，转移方程推理，优化复杂度的技巧，本笔记将一一展开。
关于转移方程，最简单无脑的办法就是假设我有无穷大的空间，开一个很多很多维的数组写转移方程，再考虑降维优化。
1.背包问题进阶
1.1.基础背包问题回顾
之前已经接触过各种背包问题，如 0-1 背包，完全背包等。
接下来给出这些基本模型的转移方程，具体不多赘述。
1.1.1：0-1 背包
通过滚动数组优化空间复杂度：$f[v]=\max\{f[v],f[v-c[i]]+w[i]\}$.
还有一种优化技巧，由于 $f[i]$ 的值仅由 $f[i-1]$ 决定，因此，可以把第一维压缩成 $2$ 个单位，转移如下：
$f[i\%2][v]=max\{f[(i+1)\%2][v],f[(i+1)\%2][v-c[i]]+w[i]\}$.
由于直接 $\bmod$ 运算常数较大，所以可以用位运算优化：
$f[i \oplus 1][v]=max\{f[(i+1) \oplus 1][v],f[(i+1)\oplus 1][v-c[i]]+w[i]\}$.
看着比滚动数组傻逼一点，但是这个技巧还是实用的。
举一个例子：[P2679 [NOIP 2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)。
~~虽然这题好像根 0-1 背包没什么关系。~~
#### 1.1.2：完全背包
和 0-1 背包只有转移顺序不同，伪代码如下：
```cpp
for i=1..N
for v=cost..V
f[v]=max{f[v],f[v-cost]+weight}
```
#### 1.1.3：多重背包
使用二进制拆分算法，代码如下：
```cpp
for (int i = 1; i <= n; i++) {
for (int weight = W; weight >= w[i]; weight--) {
// 多遍历一层物品数量
for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
}
}
}
```
### 1.2.进阶背包问题
#### 1.2.1：混合背包
这类问题的特点是结合了以上三类基础背包问题。
这类问题也不算复杂，就是结合了一下三类背包的，代码也只需要特殊判断是哪一类的物品并且使用对应的方程即可。
伪代码如下：
```
for (循环物品种类) {
是 0 - 1 背包 ? 套用 0 - 1 背包代码;
: 是完全背包 ? 套用完全背包代码;
: 是多重背包 ? 套用多重背包代码;
}
```
以下是 AC 代码：
```cpp
#include <bits/stdc++.h>
using namespace std; const int maxn = 310;
int vm,n,dp[maxn+100],w[maxn+100],p[maxn+100],v[maxn+100];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> vm >> n; for(int i = 1;i <= n;i++) cin >> w[i] >> v[i] >> p[i];
for(int i = 1;i <= n;i++)
if(p[i] == 0) for(int j = w[i];j <= vm;j++) dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
else for(int j = 1;j <= p[i];j++)
for(int k = vm;k >= w[i];k--) dp[k] = max(dp[k],dp[k-w[i]]+v[i]);
cout << dp[vm]; return 0;
}
```
#### 1.2.2：分组背包
这个问题中，物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
相比 0-1 背包，这题其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。
再说一说如何进行存储。我们可以将 $tt_{k,i}$ 表示第 k 组的第 $i$ 件物品的编号是多少，再用 $\mathit{cnt}_k$ 表示第 $k$ 组物品有多少个。
AC 代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std; const int maxn = 205;
int vm,n,t,v[maxn+100],c[maxn+100],p,cnt[maxn+100],tt[maxn+10][maxn+10],dp[maxn+10];
int main(){
memset(cnt,0,sizeof(cnt)); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> vm >> n >> t; for(int i = 1,p;i <= n;i++) {cin >> v[i] >> c[i] >> p;
cnt[p]++,tt[p][cnt[p]] = i;} //本题精髓所在
for(int k = 1;k <= t;k++) //循环每一组
for(int i = vm;i >= 0;i--) //循环背包容量
for(int j = 1;j <= cnt[k];j++) //循环每一个物品
if(i >= v[tt[k][j]]) //如果容量充足
dp[i] = max(dp[i],dp[i - v[tt[k][j]]] + c[tt[k][j]]); //转移
cout << dp[vm]; return 0;
}
```
## 2.常见背包问题优化
### 1.二进制优化
一个例子：POI 2005 Bank Notes
都是提高组的选手了，您一定知道，一个数一定可以拆分为若干个 $2$ 的整数次幂相加。
具体地说就是令 $A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)$ 分别表示由 $2^{j}$ 个单个物品「捆绑」而成的大物品。特殊地，若 $k_i+1$ 不是 $2$ 的整数次幂，则需要在最后添加一个由 $k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}$ 个单个物品「捆绑」而成的大物品用于补足。
举几个例子：
$$6=1+2+3$$
$$8=1+2+4+1$$
$$18=1+2+4+8+3$$
$$31=1+2+4+8+16$$
显然，通过上述拆分方式，可以表示任意 $\le k_i$ 个物品的等效选择方式。将每种物品按照上述方式拆分后，使用 $0-1$ 背包的方法解决即可。
### 2.四边形不等式优化
如果对于任意的 $a1 \le a2 ＜ b1 \le b2$，有$m[a1,b1]+m[a2,b2] \le m[a1,b2]+m[a2,b1]$，那么m[i,j]满足四边形不等式。
### 3.斜率优化
### 4.单调队列优化