状态压缩DP------学习小记
状态DP主要用的还是DP思想，顾名思义，加了一个状态，主要是用来求状态个数的。状态是用二进制数来表示的，也就是用0或1来表示，每一行有一个状态数，就是由这一行的0或1组成的，首先我们要获得每行的状态数。for(int i=;i<m;i++){ scanf("%d",&num); ...
洛谷 P1763 状态压缩dp+容斥原理
（题目来自洛谷oj）一天，maze决定对自己的一块n*m的土地进行修建。他希望这块土地共n*m个格子的高度分别是1,2,3,...,n*m-1,n*m。maze又希望能将这一些格子中的某一些拿来建蓄水池，即这个格子的高度应该比它周围8个格子的高度都小（超出土地范围的格子的高度算作无穷大）。现在，请你...
Corn Fields——POJ3254状态压缩Dp
Corn FieldsTime Limit: 2000MSMemory Limit: 65536KDescriptionFarmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1...
状态压缩DP----HDU4049 Tourism Planning
状态压缩动态规划感觉都不是那么好写，看网上的人说这题是2011年ACM/ICPC中的水题，暗地里感觉很是惭愧啊（花了将近4个小时），结果还算是勉勉强强地弄出来了。与往常一样，先说说题目的意思和思路，再给出代码，最后分享出代码比较精髓的地方（有的话），另这随笔主要目的是方便自己以后使用，当然很是欢迎大...
BZOJ 1087 互不侵犯King 状态压缩DP
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1087题目大意;在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。思路：状态压缩，预处理出...
HDU4539+状态压缩DP
/* 题意：n行m列的矩阵，1表示可以放东西，0表示不可以。曼哈顿距离为2的两个位置最多只能有一个位置放东西。 问最多放多少个东西。 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #incl...
HDU1565 方格取数(1)(状态压缩dp)
题目链接。分析：说这题是状态压缩dp，其实不是，怎么说呢，题目数据太水了，所以就过了。手动输入n=20的情况，超时。正解是网络流，不太会。A这题时有个细节错了，是dp[i][j]还是dp[i][q[j]]?答案是dp[i][j],因为q[j]必定会超（感谢CZ学长提示）。AC代码如下：#includ...
poj 1185 炮兵阵地(三维状态压缩dP)
题目：http://poj.org/problem?id=1185思路：d[i][j][k]表示第i行的状态为第k个状态,第i-1行的状态为第j个状态的时候的炮的数量。1表示放大炮，地形状态中1表示山地。#include<iostream>#include<cstdio>#i...
HDU3001(KB2-J 状态压缩dp)
TravellingTimeLimit:6000/3000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):8103 AcceptedSubmission(s):2642ProblemDescr...
郑厂长系列故事——排兵布阵 hdu4539（状态压缩DP）
郑厂长系列故事——排兵布阵TimeLimit:10000/5000MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmission(s):1509 AcceptedSubmission(s):554ProblemDe...
【原创】【状态压缩DP】POJ3254 Corn Fields【新手向】
一开始根本不会状压dp，上网各种找题解，但发现他们写的都很......反正我作为一个没有接触过状态压缩的，根本看不懂！然后看了好多状态压缩的题的题解，总结了一下思路，思路很重要，有了思路转换成计算机语言就好了。因此我先讲一下思路：先说说地图，地图上每一行的01代表一个状态，比如输入样例中的111、0...
HDU 3681 * Break（BFS+二分+状态压缩DP）
ProblemDescriptionRompireisarobotkingdomandalotofrobotslivetherepeacefully.Butoneday,thekingofRompirewascapturedbyhumanbeings.Histhinkingcircuitwascha...
POJ 1185 状态压缩DP（转）
1.为何状态压缩：棋盘规模为n*m，且m≤10，如果用一个int表示一行上棋子的状态，足以表示m≤10所要求的范围。故想到用ints[num]。至于开多大的数组，可以自己用DFS搜索试试看；也可以遍历0~2^m-1，对每个数值的二进制表示进行检查；也可以用数学方法（？）2.如何构造状态：当然，在此之...
POJ1185炮兵阵地（状态压缩DP)
POJ飞翔.数据弱ZQOJ飞翔 数据强Description司令部的将军们打算在N×M的网格地图上部署他们的炮兵部队。一个N×M的地图由N行M列组成，地图的每一格可能是山地（用"H"表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；...
poj 1185 炮兵阵地 [经典状态压缩DP]
题意：略。思路：由于每个大炮射程为2，所以如果对每一行状态压缩的话，能对它造成影响的就是上面的两行。这里用dp[row][state1][state2]表示第row行状态为state2，第row-1行状态为state1时最多可以安放多少大炮。则递推公式为：dp[i][K][J]=max(dp[i-1...
POJ 1185 炮兵阵地 （状态压缩DP）
题目链接Description司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用"H"表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图...
POJ3254Corn Fields(状态压缩DP入门)
题目链接题意：一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)分析：每一行看做一个状态，用一个二进制数来表示，每一行会排出牛和牛相邻的情况；...
POJ 1185 状态压缩DP 炮兵阵地
题目直达车: POJ1185炮兵阵地分析:列(<=10)的数据比较小,一般会想到状压DP.Ⅰ、如果一行10全个‘P’，满足题意的状态不超过60种（可手动枚举）。Ⅱ、用DFS搜出所有可能表示状态的整数（二进制1表示可以放，0则不能）。Ⅲ、对每一行的地行进行状态处理（p[i]表示第i行地形的状态...
luogu P2704 炮兵阵地(经典状态压缩DP)
方格有m*n个格子,一共有2^(m+n)种排列,很显然不能使用暴力法,因而选用动态规划求解.求解DP问题一般有3步,即定义出一个状态求出状态转移方程再用算法实现.多数DP题难youguan点在于第2步,而在状态压缩DP中,定义状态也是很关键的一个步骤.有关位运算的基础知识,按位与,按位或,异或等可自...
洛谷 P2704 [NOI2001]炮兵阵地 （状态压缩DP+优化）
题目描述司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H”表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在...