xkaxingz

分类

算法(1) 题解(3) 题解a(15)

/ 注册

全部文章（共3篇）

1655. 分配重复整数

很小，不难想到状压dp，且应该把状态压缩，依次枚举。有一个需要注意的地方：有时我们设置搜索状态为，表示进入到第个数，顾客的满足状态为，第个数剩余个。这样显然爆空间，无法实现记忆化，因而时间复杂度直接爆炸。解决这个问题有一个新思路：就是新增状态时，枚举当前状态的补集。因为：显然新增状态不能和现有状...

C++ 状压dp 记忆化搜索动态规划

2026-02-22

0 17

1434. 每个人戴不同帽子的方案数

套路：枚举一个变量（或者说按顺序搜索），另一个变量根据搜索路线状态压缩+记忆化处理。注意到帽子颜色很多，枚举每个帽子是否被选择不现实（共有种情况）。但同样注意到人数很少，转换一下思路：状态中表示这个人是否选好了帽子，总共种情况，从开始依次枚举帽子即可。同时结合记忆化：表示从第个帽子，状态开始选...

状压dp 动态规划记忆化搜索

2026-02-22

0 17

P1171 售货员的难题

状压dp+记忆化搜索 TSP问题：要求从出发经过所有点之后回到的最短路径。看数据量容易想到状压dp。因为要经过所有点，所以定义状态，二进制上为则表示已经过。定义为状态为，当前在点，从出发到当前状态后，达到最终状态（在点，状态为）的最短路径。于是显然有转移：。同时由于最终状态锁死，排除一些不合法...

状压dp 动态规划记忆化搜索

2026-02-21

1 24