Z_L_G
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