[DP总结]树型DP

树形DP树形DP,顾名思义,是在树上进行DP操作,因此往往需要使用DP实现,在转移时,通常先递归求出子树中的解,再在根节点进行计算转移。 树中只有两种关系,一种是父子关系,一种是平行关系。 下面是几道简单的树形DP。从中我们可以窥出树形DP的本质。

阅读全文

[DP总结]状压DP

状压DP顾名思义,是用将状态进行二进制压缩成集合的形式来方便DP转移的方法。 一些常用的代码表示如下 1234567i & j //取状态i,j重合部分i ^ j //取状态i,j不同部分i | j //合并状态i,j(1 << N) - 1 //表示111…1(N个1)1 << i - 1 //表示00100…0(1后面有i-1个0,也就是有且仅有二进制下第i位为1)for (int i = 0; i < n; ++ i) if (x & (1 << i)) cnt++; //统计当前状态x的1的个数while (x) if (x & 1) ans ++, x >>= 1; //上面的代码也可以这么写

阅读全文

{% if theme.fireworks %} {% endif %} {{ live2d() }}