状压专题
状态压缩dp(状压dp)
注：在涉及到位运算时，一定要注意位运算的优先级。该加的括号一定要加 状压dp是一类比较难理解的dp; 在讲状压dp之前，我们应该清楚所有的dp是解决多阶段决策最优化问题的一种思想方法； 请注意多阶段这三个字： 经过前面三种背包的学习，可以发现如何定义状态是解决动态规划最重要的一步； 状态的定义也就决定了相当于阶段的划分； 在背包问题中，我们通过物品的件数i和背包的容量j来定义状态或者说
【HDU】5025 Saving Tang Monk 状压最短路
传送门：【HDU】5025 Saving Tang Monk 题目分析：这题一开始想都没想就敲了优先队列+dij。。然后TLE了。。。 后来发现是一个稀疏图。。换成spfa就过了。。 这是一个四维最短路，x轴，y轴，拿到第几个钥匙，打怪的状态（状压），然后就是很简单的状压最短路了。 要注意到钥匙不用状压，因为拿到钥匙是有顺序的。 代码如下： #include <c
poj2411状压dp
题目 求把N*M的棋盘分割成若干个1*2的的长方形，有多少种方案。 例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。 如下图所示： 输入格式 输入包含多组测试用例。 每组测试用例占一行，包含两个整数N和M。 当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。 输出格式 每个测试用例输出一个结果，每个结果占一行。 数据范围 1≤N,M≤11
poj3254--Corn Fields（状压dp）
Corn Fields Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8512 Accepted: 4540 Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤
poj1185--炮兵阵地（状压dp）
炮兵阵地 Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 20169 Accepted: 7805 Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地
poj3411--Paid Roads(bfs+状压)
题目链接：点击打开链接 题目大意：有n个点，m条有向边，经过边需要一个花费，a b c p q代表 a到b的一条道路，如果经过这条边之前经过c点，那么需要p的花费，否则需要q的花费，问从1点到n点的最小花费。 方法1、每条边可能会经过多次，每个点也可以经过多次，这样就没有了边界不能直接进行dfs，因为要记录之前经过的边，所以使用状压，dis[i][j]：当前在第i个点，j表示经过了的点，这样就
SDUT 3061 聪明的玛雅 （状压DP）
题目地址：SDUT 3061 这题的比赛的时候的后台数据是错的。。。好坑啊。。。。就不吐槽出题人了。。 比赛的时候我的思路是错的，漏考虑了一种情况。应该把所有状态下的最短距离都要求出来，而我当时的思路是按照前面能选两个则选两个的贪心思路来状压，但是有的时候可以最多走奇数个并且没全走完，这种情况下就不对了。 正确思路是每次找两个没走过的状态，分成选一个和选两个两种情况来DP。然后最后找所有状态
lightoj 1037 - Agent 47 （状压DP）
题意：你现在需要消灭n个敌人，n个敌人的血量已知，你的普通攻击力为1，但是如果你杀死敌人i可以用它的武器去杀死其他敌人，p[i][j] 表示用敌人i的武器射杀敌人j会减p[i][j]滴血.问你最少可以攻击多少次可以将敌人杀死。 思路: 定义集合s为死亡敌人的集合。 dp[s] 为让集合为s的人死亡最小需要的攻击次数。 如果现在想要消灭敌人i 并且敌人i不属于s 那么dp[s | (1<<
POJ 1324 状压搜索（4进制）
给出图中蛇的范围和不可到达的地方，求蛇头到(1,1)点的最少代价 用4进制压缩存蛇身体相对蛇头的位置，BFS即可 特判蛇头在(1,1) 时的情况 注意位运算 #include "stdio.h"#include "string.h"#include "queue"using namespace std;int dir[4][2]={{-1,0},{0,1},{1,0},{0
poj3254 Corn Fields 状压dp
Language: Default Corn Fields Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 6539 Accepted: 3482 Description Farmer John has purchased a lush new rectangular pasture composed of
poj 1185 炮兵阵地（动态规划：状压DP）
用二进制数表示一行的状态 预处理记录满足条件的状态对应十进制数 因为当前行仅与上两行有关，所以状态转移方程为： dp[i][k][t] = max(dp[i][k][t], dp[i-1][j][k]+num[t]) num[t]表示状态t对应的炮台数 dp[i][k][t]表示第i行状态为t,第i-1行状态为k时对应的最大值 代码如下： #include <cstdio>#i
poj 3254 Corn Fields（动态规划：状压DP）
题意是给出一块草地，分为m*n格 某个格子为1代表可以养牛，为0代表不可以养牛 相邻的草地不可以同时养牛 问有多少种放牛的方法？ 看着别人的解题报告写的 因为相邻草地不可以同时放牛，所以我们保存可以放牛对应的状态 竖着相邻的草地也不可以同时放牛，所以如果同一列相邻两行&为真，不可以放牛 同时对于当前为0的草地也不可以放牛 把这三种情况剔除，就可以得到结果 状态转移方程为：dp[i
zoj 3905 Cake(状压dp)
题目链接：zoj 3905 Cake 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 805;struct State {int a, b;State (int a = 0, int b = 0): a(a), b(b) {}bool operat
hdu 4640 Island and study-sister（最短路+状压dp）
题目链接：hdu 4640 Island and study-sister 解题思路 用二进制数表示2~n的点是否移动过的状态， dp[s][i] dp[s][i]表示状态s上的点必须经过并且当前在i节点的最小代价， 这步用类似最短路的方式求出。 然后是 dp2[i][s] dp2[i][s]表示i个人移动过s状态的点的最小代价。 代码 #include <cstdio>#includ
HDU 5067 Harry And Dig Machine（状压dp）
HDU 5067 Harry And Dig Machine 思路：由于点才10个，在加上一个起点，处理出每个点之间的曼哈顿距离，然后用状压dp搞，状态表示为： dp[i][s]，表示在i位置，走过的点集合为s的最小代价 代码： #include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>
***Leetcode 847. Shortest Path Visiting All Nodes | 状压dp+dfs
https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 非常不错的题，状压dp，state表示已经去过哪些。 一个非常重要的剪枝是，如果一个结点的出度是x，那么如果现在是第x+1次访问这个结点，就必然是重复状态 int dp[ (1<<13)+10 ][ 13 ];int MX = INT_MAX
小明的积木 状压dp
小明的积木 题目描述 小明酷爱搭积木，他用积木搭了 n n n 辆重量为 w i w_i wi 的小车和一艘最大载重量为 W W W 的小船，他想用这艘小船将 n n n 辆小车运输过河。每次小船运载的小车重量不能超过 W W W。另外，小船在运载小车时， 每辆小车会对小船有一个损坏值 s i s_i si，当多辆小车一起运载时，该趟运载对小船的损坏值为船上所有小车的最大损坏值
Codeforces Round 938 (Div. 3)H-The Most Reckless Defense （状压dp）
来源 题目 You are playing a very popular Tower Defense game called "Runnerfield 2". In this game, the player sets up defensive towers that attack enemies moving from a certain starting point to the pla
AtCoder Beginner Contest 196 D Hanjo （dfs + 状压）
传送门 今天第一次学到给二维数组编号然后用二进制标记状态… 别人这dfs用的是真6啊 二进制状压：设这个数组的大小为n * m 那么 a[i][j] 对应的编号可以表示为(i-1) * m + j, 对应到二进制如果编号为i，如果bit & 1 << i为1表示该位置已经被使用过了。同理要想标记第i个位置：bit | 1 << i; 对应到这题因为数据很小我们可以直接遍历每一种情况，注意长
牛客小白月赛7 J 方格填色(状压DP+矩阵快速幂)
题目链接：https://www.nowcoder.com/acm/contest/190/J 题目大意：给一个m*n的方格，每个格子可以是黑色或白色，要求左右相邻两格不能同时为白色，且相邻两列不能全为黑色，问可以有几种情况数。 题目思路：由于数据范围1<=m<=5,1<=n<=1e18，所以很容易看出是状压dp。由于他要求的都是对于两列之间，也就是说行之间没有要求，所以我们只要在
ACM-ICPC 2018 南京赛区网络预赛 E AC Challenge(状压DP)
题目链接：https://nanti.jisuanke.com/t/30994 题目大意：有n道题，每道题做出来会得到t*a[i]+b[i]分，但是有些题目有先决条件，需要先完成某些题目才能写，问最多能得到多少分 题目思路：这道题需要用二进制的做法。首先先用二进制表示每道题的先决条件，放入pre数组，第几位是1就是需要先写第几题。然后就把所有的情况全部枚举出来，由于一共就20题，一
HDU 4352 XHXJ's LIS(数位DP+状压)
Problem Description #define xhxj (Xin Hang senior sister(学姐)) If you do not know xhxj, then carefully reading the entire description is very important. As the strongest fighting force in UESTC,
poj1185 AcWing 292. 炮兵阵地（状压dp）
司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用”H” 表示），也可能是平原（用”P”表示），如下图。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 1185_1.jpg 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻
BZOJ1076. [SCOI2008]奖励关（期望dp/状压/逆序）
题目描述 你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物， 每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。 宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1次系统都抛出宝物1（ 这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n
BZOJ1231: [Usaco2008 Nov]mixup2 混乱的奶牛（状压DP）
Description 混乱的奶牛 [Don Piele, 2007] Farmer John的N(4 <= N <= 16)头奶牛中的每一头都有一个唯一的编号S_i (1 <= S_i <= 25,000). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感. 如果一个队伍里任意两头相邻