警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「笔记」day2 - DP

:warning:注意:这是ZROI集训的源笔记,其中有很多缺失和遗漏以及无法看懂的部分,大家就不要看了吧。

以下是原笔记:


day1欠账

简单题

\(f_{n,x,y}\)长度\(a\)\(x,y\)表示\(1\)\(0\)的奇偶性。

\(f_{n,0,y} -> f_{n,0,y\ xor\ 1}\)

\(f_{n,x,0} -> f_{n,x\ xor\ 1,0}\)

矩阵优化

\(f_{n+1,0,0}, f_{n+1,0,1}, f_{n+1,1,0}, f_{n+1,1,1}\)

\(0\) \(0/1\) 不放 \(1\)

转移矩阵 \[ \left[ \begin{array}{c} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \end{array} \right] \]

树形DP

重点!如果合并两个子树时间是两个子树的乘积,那么这个树形DP是平方的

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

void merge(int x, int p) { // 合并子树
f[p][0] = f[p][1] + /* max(f[k][0], f[k][1]) */;
f[p][1] = f[p][0] + f[x][1];
}

void init(int x) { // 初始化
// f[k][0] = 0;
// f[k][1] = 1;
}

void treedp(int x) { // 树形dp 不需要改
for (int i = 0; i < c[x].size(); i++) {
treedp(c[x][i]);
}
init(x);
for (int i = 0; i < c[x].size(); i++) {
merge(c[x][i], x);
}
}

int main() {
// 状态 -> init -> merge
}

最大独立集

同模板

例题2

1
2
3
4
5
6
state:	f[i][0], f[i][1]
init : f[i][1] = f[i][0] = 0;
merge: f[x][1] = max(f[p][1] + max(f[x][1], f[x][0]),
f[p][0] + f[x][0] + 1);
: f[x][0] = f[p][0] + max(f[x][1], f[x][0]);
// 缺失部分

例题3

1
2
3
4
5
state:	f[i][0] 我不是,孩子也不是[不合法]
: f[i][1] 我不是,孩子是[合法]
: f[i][2] 我是[满足]
init : f[i][0] = 0, f[i][2] = 1, f[i][1] = 0x3f3f3f3f
merge:
x 0 1 2
0 2
1 0 1 2
2 1 1 2

HOMEWORK:距离为\(2\)

例题4

简化版(只考虑子树)

1
2
3
4
5
f[i][x][y] 当前子树关键点 当前子树的子树

f[i][0][0] = 0
f[i][1][0] = 1
f[i][0][1] = f[i][1][1] = 0x3f3f3f3f
x 0,0 0,1 1,0 1,1
0 0,1 1,1
1 1,0 1,1 1,0 1,1

普通版

  • 存在度数大于\(3\)的点

贪心地选一个度大于\(3\)的点为根,然后同简化版

  • 不存在(链),输出\(1\)

例题5

1
2
3
4
5
6
7
f[i]表示只删以i为根的子树的ans(minimal maximum)

f[叶子]=0x3f3f3f3f
f[其它]=0

merge:
f[i]=max(f[i], x);

练习1

1
2
3
4
  0 1
---
0|0 1
1|0 x

ans = 5471492

[暂缺]

例题6

简化版(只考虑子树)

\(f_f=\max(f_f, f_j-w_j)\)

普通版

令子树外最长路为\(u_i\)

维护次大值\(g_f\)\(f_f\)的来源\(where_f\)

\(g_f\)初始\(0\)

1
2
3
4
if (f[k] + w > f[f]) {
g[f] = f[k];

}
1
2
3
4
5
6
User -> Web: Submit
Web -> Judger: Submit
Note right of Judger: Waiting & Judging
Judger -> Web: WA
Web -> User: WA
Note left of User: MMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
start=>start: 做题
needIOOptimize=>condition: 需要快速IO?
kengDie=>operation: 坑爹,命题人SB
implementation=>condition: 大模拟题?
codeLong=>operation: 难写,命题人SB
constant=>condition: 题目还卡常?
boring=>operation: 无聊,命题人SB
isEasy=>condition: 题目太简单?
water=>operation: 太水,命题人SB
end=>end: 婊死出题人

start->needIOOptimize
needIOOptimize(yes)->kengDie->end
needIOOptimize(no)->implementation
implementation(yes)->codeLong->end
implementation(no)->constant
constant(yes)->boring->end
constant(no)->water->end

例题7

令每条边经过\(f_i\)次,那么\(ans = \sum d_if_i\)\(d_i\)是权值。

dfs求出\(f_i\)即可。

监测站

乱搞

树形背包

\(f_{i,j}\)表示\(i\)子树\(j\)容量

\(g_{i,j}\)表示不选\(i\)的子树\(j\)容量

初始\(g_{i,j}=0\)

如果选\(i\)就一定选整个子树 :\(max(g_{i,j},\sum v_i)(j \ge \sum v_i)\)

\(g'_{i,a+b}=g_{i,a}+f_{c,b}\)

\[ f_{i,j}=\left\{\begin{array}l g_{i,j} & j>\sum v_i,\\ max(g_{i,j}, \sum v_i) & j\ge \sum v_i. \end{array}\right. \]

时间复杂度\(O(n^3)\)

状压DP

例题1

\(f_{i,p[n]}\)\(i\)衣服,\(p_i\)裤子是否配对。

for j=1...n

(i+1, j)可配对,\(p_j=0\)

f[i+1][j|(1<<(j-1))] += f[i][j];

1
2
3
4
3 9
1 1 1 2 1 3
2 1 2 2 2 3
3 1 3 2 3 3

例题2 拓扑排序计数(NP-Hard)

\(f_p\)选的点数。

对于所有满足要求的(k, j)\(j\)没被选,\(k\)放了,\(f_{p|(1<<(j-1))} += f_p\)

\(20: 2^n\)

\(18: 2^nn\)

\(16: 2^nn^2 / 3^n\)

例题3

\(t_i\)代表第\(i\)条直线覆盖点的。

\(f_p=\min(f_{p|t_i},...,f_p+1)\)

固定一个端点,可以将枚举直线改为\(O(n)\)

2n个点最短路乱搞?

例题4

Who knows?

for i=1..m

\(f_{p|t_i}=\max(..., f_p+1)(p\&t_i=0)\)

例题5 最长简单环(NP-Hard NPC)

实现例题2 (选做例题5)