Z_L_G

分类

总结(12) 训练赛(6) 题解(85)

/ 注册

全部文章（共6篇）

状压dp

什么是状压对于题目中一种复杂的状态，如多维，多行，多条路，某种方案，某种集合等压缩成一个整数的过程就是状态压缩这也可以看作是一个Hash的过程除去压缩状态的过程，其实它整体和普通的dp差别不大，都是从已知过程推向位置过程压缩的意义在于把一个一般无法描述的状态，变成一个包含多种信息的状态，而...

状压dp

2025-07-06

0 7

算法入门-Mondriaan's Dream

题意 n行m列矩形，用1*2的矩形块填充，有多少种填充方案思路依然是棋盘放置一类的问题，考虑一行一行放对于每一行，上一行竖着放的地方一定放不了，上一行横着放的地方可以竖着放也可以横着放，行内不可能的是把一个横着的拆开，两行间不可能的是，上一行竖着，这一行还放东西设计状态：横着放记为0，...

状压dp 好题

2025-07-05

0 8

算法入门-Most Powerful

题意 n个原子，两个原子i，j碰撞会释放能量，并且j会消失，求n个原子能产生的最大能量思路状压dp 每个原子去碰撞的时候，要还剩下哪些原子也就是每次从还存在的原子中挑出两个原子碰撞，并选择一个消失最终剩下一个原子结束状态压缩是你过程，从全满，到只剩一个特别的，在st=0的时候要人为...

状压dp

2025-07-03

0 13

TSP问题

题意旅行商问题，在一个若干点的图中，设计一条最短路径，途径所有点有时最终会要求回到原点思路状压dp 访问每一个点的时候需要考虑当前已经访问了哪些点走到某一个点的最短路径应该是所有(上一步最短路径+上一步所在点到当前点距离)取最小表示当前状态为st，最后一个点时i的最短路径代码...

状压dp

2025-07-03

0 11

算法入门-炮兵阵地

题意给定N*M的地图，包含山地和平地，山地不能布置炮兵炮兵会攻击自己上下两格，左右两格的位置，请问在炮兵相互不打架的情况下，地图上最多放置多少炮兵思路仍旧按行考虑，预处理行内可行状态枚举每行可能性，和前两行状态有关，所以是一个三维的dp 表示第i行状态j，i-1行状态为k 代码 ...

状压dp

2025-07-02

0 9

算法入门-[SCOI2005]互不侵犯KING

题意有一个N*N(N<10)的棋盘，其中需要放置K个国王，国王会攻击以他为中心的九宫格范围内的棋子，要是所有国王互不攻击，总共有多少种方案思路如果按顺序从上到下，从左到右，每次放置新的国王的时候都需要考虑它左边和上侧的国王，状态过于复杂难以描述由于N不大可以考虑一行一行放置，这样...

状压dp

2025-07-02

0 16