动态规划。
最经典的哈密顿回路的题就是ACwing动态规划基础课的题和算法进阶指南中的了,都是用于讲解状压dp的。(但我还是没想到)
f [ i ] [ j ] f[i][j] f[i][j] 表示从起点(任意)走到 j j j ,经过的所有点用状态 i i i 表示,所有的方案数。 i i i 被我们认为是个二进制数,每一位表示从起点到 j j j 是否经过对应的点。从最低位到最高位分别对应点 0 ∼ n − 1 0\sim n-1 0∼n−1,状态 i i i 的第 k k k 位(从低到高,从 0 0 0 开始)二进制位为 1 1 1 表示状态 i i i 经了第 k k k 个点(从 0 0 0 开始),当对应位为 0 0 0 时同理。
转移方程本质上就是由倒数第二个点来推出 j j j。假设当前计算 f [ i ] [ j ] f[i][j] f[i][j],那么经过状态 i i i 到达 j j j 的方案数等于从起点不经过点 j j j 到达全部与 j j j 点可达的点 k k k 方案数,也就是 s → . . . → k → j s\rightarrow...\rightarrow k\rightarrow j s→...→k→j。显然,如果不可达就不能加。
初始化, f [ s ] [ 0 ] = 1 f[s][0]=1 f[s][0]=1,表示自己到自己是一种方案。
最后我们只需要累加经过全部点,且能与起点可达的方案数即可。因为本题的起点是 1 1 1,所以与任何数的最大公因子都是 1 1 1,即与任意一点都可达,所以将全部非起点的方案数累加即可。
一定要注意对于解决哈密顿回路问题的状压dp是单源解法,即只能计算固定起点到其他点的方案数或最小路径等。而且起点信息并不体现在状态定义和状态转移中。
代码#include
using namespace std;
typedef long long LL;
const int N = 22;
int n = 5;
LL ans;
int st[N][N];
LL f[1
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?