动态规划（DP）学习笔记

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

数位 DP

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

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

树形 DP

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

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

状压 DP

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

//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)$，建议使用下面的

//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]);

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

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 函数值的异或和

// 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;
        }
}