铜牌-

博弈，状态数计算

0/1背包+分组背包

转化成分组背包后状态数足够少

博弈，观察+硬推结论

bitset优化完全背包+观察

另一种做法：在做完全背包，要求选择的物品恰好重量为w时，可以构造一个重量为1，价值为0的物品，将问题转化为选择的物品重量小于等于w

铜牌+~银牌-

对某一类/某一模式字符串的计数问题

枚举字符串的关键特征，dp计算其余部分的可行方案数

bitset+折半查找

树上问题套了个博弈壳

某类要求最大化己方得分-对方得分的博弈问题

设计状态时$f(i,0/1)$表示当前状态为i，当前操作者为先/后手时得分差的最大值

若后继状态为j，则有转移$f(i,0)=\min\{[increment(i\rightarrow j)]-f(j,1)\}$

比较容易想到的状态设计和转移dp

$O(n^2)$二维状态设计，前缀和优化、桶优化

区间选择相关的dp问题

去除存在包含关系后的区间，此时剩余区间的左右端点同时具有单调性

期望dp

差分法计算$x^2$期望，即将$x^2$拆成$1+3+\cdots+(2x+1)$

形如$f[x]=A+pf[x]$的转移方程，可移项得到$f[x]=\frac{A}{1-p}$

技巧性比较强，状态压缩，折半查找

bitset练习题

wqs二分典中典

巧妙的状态设计

在单调栈形成的链上进行状态转移，结合前缀和思想

观察后转化为一个比较简单的二维dp，也可以直接用组合方法做