Z_L_G

分类

总结(19) 训练赛(12) 题解(103)

/ 注册

全部文章（共132篇）

算法入门-Min酱要旅行

题意有k个物品，每个物品有体积，求空间为1~m，不带第1~k件的方案数思路无法考虑枚举不带某一个物品，对剩下的物品01背包，复杂度直接爆炸反向思考，可以求解k个物品装满m空间的01背包(每个物品用一次，恰好装满指定体积)，然后再减去必须取某一个物品装满m空间的方案数，就得到去掉某一个物...

多次dp 01背包

2025-07-07

0 26

最大全0子矩形问题

题意对于一个由0,1构成的矩形，求解其中面积最大的全0子矩形，和全0子正方形思路法一：枚举上下左右四个边界，利用二维前缀和，如果前缀和为0就成立复杂度：法二：枚举左右边界，对边界内的1按y排序，每两个相邻点+边界构成矩形复杂度：,(m为1的个数，最多到) 法三：悬线法，...

dp

2025-07-06

0 20

状压dp

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

状压dp

2025-07-06

0 25

算法入门-Mondriaan's Dream

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

状压dp 妙妙题

2025-07-05

0 21

算法入门-[NOIP2008]传纸条

#双线dp 双线表示同时有两种状态，且会相互影响题意给定M*N的地图，每个点有val，每个点只能走一次从左上走到右下再走回左上，且向下的过程只能向下向右，向上的过程只能向上向左走完最多获得的val是多少思路思路一：严格按照一圈走无法完成，走下去的过程走过的格子会影响走上去的过程...

双线dp

2025-07-05

0 21

算法入门-Most Powerful

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

状压dp

2025-07-03

0 23

TSP问题

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

状压dp

2025-07-03

0 22

算法入门-炮兵阵地

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

状压dp

2025-07-02

0 17

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

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

状压dp

2025-07-02

0 28

算法入门-小A买彩票

题意买彩票，3元一张，中1,2,3,4元的概率相等买n张，求不亏的概率输出要求：最简分数，如果概率为0就输出"0/1"，概率为1就输出"1/1" 思路类似昨天弹球的问题状态转移可以靠钱勾连表示买了i张彩票赚j元的可能最后求一个GCD就行，注意只要买了就会亏，所以概率为1只有可能...

dp 概率

2025-06-28

0 26