动态规划（DP）学习笔记

动态规划（Dynamic Programming）本质上是图论问题。

数位 DP

按照数字的位数划分转移阶段 转移方式：枚举下一位数字填什么 限制条件：数位的上下界要求

[1, r] 区间数字个数
[l, r] 区间数字个数
[1, r] 区间最大值

树形 DP

按照树从根往下或者叶子网上划分阶段 转移方式：集合叶子或者父亲的信息 限制条件：不详

给定一棵 N 个点的树，求有多少点
给定一棵 N 个点的树，求最大点权值
给定一棵 N 个点的树，求树的直径

状压 DP

枚举子集并把所有子集合并

cpp

//4^n
for (int a = 1; a < (1 << n); a++)
	for (int b = 1; b < a; b++)
		if ((a | b) == a) f[a] = merge(f[b], f[a ^ b]);
		// (a | b) == a 判断 b 是否为 a 的子集

上面的代码复杂度为 $O(4^n)$ ，建议使用下面的

cpp

//3^n
for (int a = 1; a < (1 << n); a++)
	for (int b = a; b; b = (b - 1) & a)
		f[a] = merge(f[b], f[a ^ b]);

枚举最后一个加进来的数再合并

cpp

for (int a = 1; a < (1 << n); a++)
	for (int b = 1; b <= n; b++)
		if (a & (1 << (b - 1))) work(a, b);
		// f[a ^ (1 << (b - 1))] => f[a]

博弈论 DP

必胜态和必败态

必胜态：存在一个操作能使当前状态转移到必败态。 必败态：所有终止的状态都是必败态，或者该状态上的所有操作都会转移到必胜态。（不能一步走到必胜态）

SG 函数

如果游戏状态转移构成一个 DAG

SG(x) 为不在后继结点数值集合中的最小非负整数
终止态的 SG 函数值为 0
必胜态的 SG 函数值大于 0
必败态的 SG 函数值等于 0

复合游戏的和

SG 定理：复合游戏的 SG 函数值等于子游戏的 SG 函数值的异或和

cpp

// Nim Game 求 SG 值
sg[0] = 0;
for (int a = 1; a <= n; a++) {
	int cnt = 0;
	for (int b = 1; b <= a; b++)
		z[++cnt] = sg[a - b];
	sort(z + 1, z + cnt + 1）；
	for (int b = 0, c = 1; ; b++)
		if (z[c] == b)
			while (z[c] == b) c++;
		else {
			sg[a] = b;
			break;
		}
}