likeJ

状态压缩

# Hash 和 Hash 表(1) # kmp 算法(1) # LCA（最近公共祖先）(1) # 二分(2) # 广搜bfs(16) # 树形dp(3) # 深搜dfs(8) # 贪心(4) # 递推(6) 1024程序员节(1) c++杂题(3) hash(4) STL(1) ST表(1) 二分图(5) 信息奥赛一本通——高效进阶(13) 动规dp(17) 单调栈(6) 单调队列(8) 图论(1) 并查集(9) 快速幂(2) 拓扑排序(6) 数论(2) 最小生成树(3) 最短路径(15) 未归档(4) 树状数组(4) 矩阵乘法(2) 离散化(4) 线段树(5) 赛后分析(88) 邻接表(2)

/ 注册

全部文章 / 状态压缩（共7篇）

状态压缩（状态压缩）

状态压缩（状态压缩）注：在涉及到位运算时，一定要注意位运算的优先级。该加的括号一定要加定义状态（例如）求每一种放法的背包价值，状态应该是这n件物品的放与不放的情况。最容易想到的是开个n维数组，第i个维度的下标如果是1的话代表放第i件物品，0的话代表不放第i件物品；但是这...

2021-03-26

0 313

车（状压dp）

车 Description 在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。 Input 第一行为棋盘的大小n 第二行为障碍的数量m 第三行到第m+3为m个障碍 Output 总数 Sample Input 4 2 1...

2021-03-26

0 359

车II（状压dp）

车II Description 有一个nm的棋盘(n、m≤80,nm≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻。求合法的方案总数。 Input n,m,k Output 方案总数 Sample Input 3 3 2 Sample Output 24 解题...

2021-03-26

0 421

P2704 [NOI2001]炮兵阵地（状压dp）

炮兵阵地题目传送门 Description 司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部...

2021-03-26

0 364

P1433 吃奶酪（状压dp）

吃奶酪题目传送门解题思路我们可以设一个f[i][j] i表示，当前在i点，j表示一个二进制，其中0表示没走过，1表示走过 f [ j ] [ i ] = m i n ( f [ j ] [ i ] , d o u b l e ( 1.0 ∗ f [ k ] [ i − ( 1 <...

2021-03-26

0 478

P2622 关灯问题II（状态压缩优化）

关灯问题II 题目传送门解题思路它的起点是一定的，终点也一定，求最小步数，满足边权都为1，很明显是一道状压BFS 将它的状态存到队列里，一开始全部为1 转移我们设a[i][j]表示第i个开关可以改变第j个灯当a[i][j]为1，并且当前状态的第j位为1时，则当前状态为当前状态异或...

2021-03-26

0 824

P1879 [USACO06NOV]Corn Fields G（状压dp）

[USACO06NOV]Corn Fields G 题目传送门解题思路这题就用一个f[i][s[j]] 表示在当前第 i 行的状态为 s[i] f [ i ] [ s [ j ] ] + = f [ i − 1 ] [ s [ w ] ] f[i][s[j]]+=f[i−1][s[w...

2021-03-26

0 633