【BZOJ 4455】[ZJOI2016] 小星星

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4455
神犇题解:http://www.cnblogs.com/DaD3zZ-Beyonder/p/5793086.html

解题报告

这题这个阶乘级别的状压DP大家都会吧?

$f(i,j,S)$ 表示树上第$i$个点,对应图中第$j$个点,子树中的对应状态状压后为$S$的方案数

然后我发现了两件事:
1. 这样会T
2. 我不会更优的算法了

正解的话,用了一个非常神奇的DP
考虑枚举有图中有哪些点被映射,然后 $O(n^3)$ 就可以求出满足边的限制的方案数(但点不一定是一一对应的)
然后我们加上点数刚好的情况,减去点数差一的情况,加上相差为2的情况…
于是我们就可以在 $O(2^n \cdot n^3)$ 的时间复杂度内解决这个问题啦!