DP-2024寒假外培
Drest
·
·
算法·理论
DP
DP 三要素
- 状态
- 转移（状态之间的关系）
- 初始化（状态的边界条件）
设计状态的方法
找到题目中所有变化的量
一个DP题无法解决，唯一原因是维度不够，加维一定能解决问题。
例题
- P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles \checkmark
状态：f[x][y] \to 价值
- 数字三角形但是%100
如果按照上一道题，无法正确DP，说明维度不够，要加维。
状态：f[i][i][k] \to 走到 (i,j) 价值%100 = k 是否可能。
- 区间染色
f[i]表示染色到i最小的代价
DP 的分类
- 背包DP
- 区间DP
- 树形DP
- 数位DP
- 状压DP
- 排列DP
- 博弈DP
- 一般DP（最难）
- 插头DP（不考）
- 期望DP（没套路）
排列DP
研究对象
### 转移
排列DP的转移方法：把所有数从小到大/从大到小一个个插入。
### 状态
$f[i]... \to i$ 已经被插入
### 例题
$1 - n(n\le10^6)$ 的所有排列中逆序对个数为偶数的有多少个？
$f[i][j] \to$ $1 - i$ 已经被插入，当前有 $j$ 个逆序对时，方案个数。
转移：从小到大插入，将 $i + 1$ 插入到 $k$ 位置时，会新增 $i - k$ 个逆序对，即 `f[i + 1][j + i - k] += f[i][j]` 。
初始化：插入 $1$ ，有 $0$ 个逆序对的方案数只有 $1$ 种，即 `f[1][0] = 1` 。
```cpp
//状态第一个维度f[i] 一定代表已经插入到到 i
//转移方法:把所有数从 小到大或者从大到小插入枚举新插入的数的位置
cin >> n;
//求1-n的排列有多少个排列有偶数个逆序对
// f[i][j] 表示1-i已经插入有j个逆序对的方案数
f[1][θ]=1;
//O(n^4)
for (int i=1;i<n;i++)// 已经插入1-i 接下来要插入i+1这个数
for (int j=0;j<=i*(i-1)/2;j++)// 当前有个逆序对
for (int k=0;k<=i;k++)// 枚举i+1要插入到哪里
f[i+1][j+i-k] += f[i][j];
```
但是，不难看出，这是 $O(n^4)$ 的代码，因为 $j$ 非0即1，所以可以优化成：
```cpp
// f[i][j]表示1-i已经插入有j个逆序对的方案数j:0/1
f[1][0]=1;
//0(n^2)
for (int i=1;i<n;i++)//已经插入1-i 接下来要插入i+1这个数
for (int j=0;j<=1;j++)// 当前有个逆序对
for (int k=0;k<=i;k++)// 枚举1要插入到哪里
f[i+1][(j+i-k)&1] += f[i][j];
```
## 背包DP
### 状态
$f[i][j] \to$ 前 $i$ 个物品考虑完毕用掉了 $j$ 的体积所能获得的最大价值。
### 01背包问题
f[i][j]:前i个物品用了j的体积所能获得的最大价值
```cpp
for (int i=1;i<=n; i++ )
for (int j=0;j<=m;j++)// 要求f[i][j]
{
f[i][j] = f[i-1][j];//不选
if (j>=v[i]) f[i][j]=max(f[i][j]， f[i-1][j-v[i]]+W[i]);//选
}
```
### 多重背包 + 二进制优化
```cpp
#include <iostream>
using namespace std;
const int N =1e7 + 10;
int q[N], v[N], w[N], s[N];
int main() {
int n, m;
cin >> m >> n;
int cnt = 0;
for (int i = 1; i <= n; i++) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while (k <= s) {
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0) {
cnt ++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}
n = cnt;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
q[j] = max(q[j], q[j - v[i]] + w[i]);
}
}
cout << q[m];
return 0;
}
```
## 数位DP
### 转移方法
从高位开始，一位一位地填 $y$ 的值。
### 状态
$f[i][0/1] \to$ 从高到低填完第 $i$ 位，$0\to < x, 1\to = x$ ，方案数。
### 初始化
给 $x$，$y$ 两个数前加 $0$，即 `f[n+1][1]=1;` ，同时，还需要清空数组。
```cpp
int dp(int z){
int n = 0;
while (z != 0) {
n++;
x[n] = z%10;
z/=10;
}
//f[i][j]表示已经填完y[n~i] j=0代表y<x j=1 代表y=x时的方案数
memset(f,0,sizeof(f));
f[n+1][1]=1;
for (int i=n;i>=1;i--)// 当前要填y[i]的值此时已经填Ty[i+1~n]
for (int j=0;j<=1;j++)// 在填y[i]之前是<还是=
{
int up=9;//y[i]能填的最大值
if (j==1) up=x[i];
for (int k=0;k<=up;k++)// 枚举y[i]填k
f[i][(j==1)&&(k==up)] += f[i+1][j];
}
return f[1][0] + f[1][1];
}
```
## 区间DP
### 第一类区间DP
特征：相邻，区间，合并。
#### 状态
`int f[maxn][maxn]; // 代表把l~r堆石子合并成一堆的最小代价 `
#### 转移方法
枚举一个分界点，合并[左~分界点] 和[分界点+1~右]
#### [经典例题-石子合并](https://www.luogu.com.cn/problem/P1775) $\checkmark
#include <bits/stdc++.h>
using namespace std;
const int N = 500;
int n;
long long a[N], qz[N], dp[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
qz[i] = qz[i - 1] + a[i];
}
for (int len = 2; len <= n; len++)
{
for (int i = 1, j = i + len - 1; j <= n; i++, j++)
{
dp[i][j] = 1e19;
for (int mid = i; mid <= j; mid++)
{
dp[i][j] = min(dp[i][j], qz[j] - qz[i - 1] + dp[i][mid] + dp[mid + 1][j]);
}
}
}
cout << dp[1][n];
return 0;
}
第二类区间DP
...
树形DP
在树上做的DP
转移方式
把所有儿子信息整合
状压DP
状态
### 初始化
从 $0$ 号点出发，所以 `f[1][0] = 0`。
```
#include<bits/stdc++.h>
using namespace std;
int n;
int f[1<<20][20];
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
for (int i = 0; i < (1<<n); i++)
for (int j = 0; j < n; j++)
f[i][j] = 1e+20;
for (int i = 0; i < (1<<n); i++)
for (int j = 0;j < n; j++)
if (i & (1<<j))
for (int k = 0; k < n; k++)
if ((i & (1<<k)) == 0)
f[i|(i<<k)[k]] = min(f[1|(1<<k)][k], f[i][j]+dis(j,k));
double ans = 1e+20;
for (int i = 0; i < n; i++)
ans = min(ans, f[(1<<n)-1][i] + dis(i, 0));
cout << ans << endl;
return 0;
}
```
## 矩阵乘法优化DP
### 特点
- $f[i]$ 只和 $f[i - 1]$ 有关。
- 转移系数 $m$ 与 $i$ 无关。
## 博弈论DP
### 第一类博弈论问题
针对一个游戏，用必胜必败态做。
### 状态
状态 = 游戏状态，表示当前状态是否必胜。
$bool\ f[i] \to$ 到 $i$ 时先手必胜/必败。
### 转移方法
转移要按照游戏规则进行操作，要看能否转移到一个必败态。
如果能转移到必败态，那么就是必胜，否则就是必败。
所有能转移到的状态中，如果有 $false$，那么自己的取值就为 $true$。
```cpp
bool f[maxn], vis[maxn];
void dfs(int i) { // 求数为 now 时候是必胜还是必败
if (i <= 0) return true;
if (vis[i]) return f[i];
vis[i] = true;
f[i] = false;
for (int j:{1, 2, 4, 8})
if (!dfs(i - j)) f[i] = true;
return f[i];
}
```
---
### 第二类博弈论问题
针对多个游戏，用 sg 值来做，把每个游戏的 sg 值异或起来得到答案（sg 定理）。
### 做法
1. 用 sg 值做 dp。
2. 转化为 Nim