简单状压dp的思考

简单状压dp的思考

本文参考：CPH ，USACO Guide

（大佬请越过，这是初学笔记，不要吐槽内容）

前置知识，位运算基础，动态规划基础

一个很让萌新望而却步的粗略说法，状态是元素的子集的动态规划算法可以用位运算来高效的优化。

那么第一道题就应声而来：

哈密顿航班 cses.fi/problemset/task/1690

我觉得这道题会花费很长时间，但是这题不算难，首先要自己尝试。（解析在下面啦）

题目意思是给定一个很小的图，从1号点到N号点，每个点恰好走一次有几种方案？

看过这道题，你是否想到了旅行商问题？没错，这是一个没有保证正确的多项式时间复杂度的算法的问题。好吧，至少方向是有了。O(n!)枚举，这是一个很贴合n范围的算法。但是显然他还需要再快一点。

不去思考如何优化，一般的思路是考虑在枚举中我们浪费了哪些时间。如果这个算法还可以做最优，那么一定是有哪一些重复计算。因为动态规划的本质就是利用记忆化来减少重复计算。在不考虑动态规划的情况下，大多数暴力算法也可以先考虑哪些计算重复。

那么在这个哈密顿航班的问题里边，我们发现如果固定了一些点集和一个结尾，就能根据它算出所有点。

如果用动态规划的思路来思考的话，如果我们已经求得了点集S从1走到i的答案，那么其他答案就可以由这个状态推出。因为在这个问题里面每个状态只需要知道走到哪里和还有哪些点需要走。这道题就是这么做的。

这样我们把复杂度优化到O(2^n n)级别。

CF1316E Team Building

USACO 1089 Gold Uddered but not Herd

这两道题都是