您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

2021年蓝桥杯A组省赛-回路计数

不牌不改 发布时间:2022-03-26 21:58:41 ,浏览量:0

题目

请添加图片描述

题解

动态规划。

最经典的哈密顿回路的题就是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            
关注
打赏
1662186765
查看更多评论
0.0644s