hdu_4352_XHXJ's LIS(数位DP+状态压缩)
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4352 题意：这题花大篇篇幅来介绍电子科大的一个传奇学姐，最后几句话才是题意，这题意思就是给你一个LL范围内的区间，问你在这个区间内最长递增子序列长度恰为K的数有多少个 题解：数位DP+状态压缩，这题首先...
hdu 2825(ac自动机+状态压缩dp)
题意：容易理解...分析：在做这道题之前我做了hdu 4057，都是同一种类型的题，因为题中给的模式串的个数最多只能为10个，所以我们就很容易想到用状态压缩来做，但是开始的时候我的代码超时了dp时我们由dp[i][j][k]枚举其后接的字符转移到dp[i+1],在枚举前判断下是否有dp[i][j][...
HDU 2809 God of War（DP + 状态压缩）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2809题目大意：给出战神吕布的初始攻击力ATI、防御力DEF、生命值HP、每升一级增加的攻击力In_ATI，增加的防御力In_DEF和增加的生命值In_HP。然后给出n个敌人的攻击力、防御力、生命值和杀死...
hdu4352 XHXJ's LIS(数位DP + LIS + 状态压缩)
#define xhxj (Xin Hang senior sister(学姐)) If you do not know xhxj, then carefully reading the entire description is very important. As the strongest f...
POJ3254 - Corn Fields(状态压缩DP)
题目大意给定一个N*M大小的土地，土地有肥沃和贫瘠之分(每个单位土地用0,1来表示贫瘠和肥沃)，要求你在肥沃的单位土地上种玉米，如果在某个单位土地上种了玉米，那么与它相邻的四个单位土地是不允许种玉米的，问你有多少种种玉米方案。(不种一算一种方案)题解很基础的状态压缩DP，我们可以逐行的进行状态转移，...
Codeforces 903F Clear The Matrix（状态压缩DP）
题目链接 Clear The Matrix题意 给定一个$4 * n$的矩形，里面的元素为$'.'$或$'*'$。现在有$4$种正方形可以覆盖掉$'*'$，正方形的边长分别为$1,2,3,4$。求把整个矩形变成全$'.'$的最小代价。考虑状压DP设$f[i][j]$为前$i$列已经全部变成'.'，第...
poj 2923(状态压缩dp)
题意：就是给了你一些货物的重量，然后给了两辆车一次的载重，让你求出最少的运输次数。分析：首先要从一辆车入手，搜出所有的一次能够运的所有状态，然后把两辆车的状态进行合并，最后就是解决了，有两种方法：1.组合解决:代码实现：#include<cstdio>#include<cstrin...
poj 3254 状态压缩DP
思路：把每行的数当做是一个二进制串，0不变，1变或不变，找出所有的合法二进制形式表示的整数，即相邻不同为1，那么第i-1行与第i行的状态转移方程为dp[i][j]+=dp[i-1][k]；这个方程得前提条件是num[i][j]&num[i-1][k]==0，也就是他们表示的二进制形式相与为0...
Mondriaan's Dream(POJ 2411状态压缩dp)
题意:用1*2的方格填充m*n的方格不能重叠，问有多少种填充方法分析：dp[i][j]表示i行状态为j时的方案数，对于j,0表示该列竖放（影响下一行的该列），1表示横放成功（影响下一列）或上一列竖放成功。状态转移时，枚举每一行可能的状态上一行取反得下一行能放的状态。#include <map&...
POJ 3254 状态压缩 DP
B - Corn FieldsCrawling in process... Crawling failed Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %lluSubmit StatusDescr...
HDU 1074 Doing Homework（DP状态压缩）
题意：有n门功课需要完成，每一门功课都有时间期限以及你完成所需要的时间，如果完成的时间超出时间期限多少单位，就会被减多少学分，问以怎样的功课完成顺序，会使减掉的学分最少，有多个解时，输出功课名字典序最小的一个。 作业最多只有15个，容易想到是状态压缩 dp[i]表示i对应状态的最小扣分 i转换为...
HDU1074 Doing Homework 状态压缩dp
题目大意： 根据完成任务的截止时间，超时一天罚1分，求完成所有任务后的最小罚时 这里n最大为15，可以利用状态压缩来解决问题 1 /* 2 首先要明白的一点是状态1/0分别表示这件事做了还是没做 3 而1/0的位置表示这是哪一件事 4 比如说 5 可以表示为101，那么表示第一个和第三个任...
hdu 1074 Doing Homework 状态压缩DP
题意：给出n个作业的名称，死线，用时，每个课程每超过死线一天扣一分，求最小扣分及其排列，多种情况下输出字典序最小的一组。 由于n最大只有15，所以用状态压缩，从1到1<<n遍历，若该状态下包含课程j已完成（i&1<<j==1)并且当前完成j的分数最少，更新该状态。 最...
状态压缩DP----HDU4049 Tourism Planning
状态压缩动态规划感觉都不是那么好写，看网上的人说这题是2011年ACM/ICPC中的水题，暗地里感觉很是惭愧啊（花了将近4个小时），结果还算是勉勉强强地弄出来了。与往常一样，先说说题目的意思和思路，再给出代码，最后分享出代码比较精髓的地方（有的话），另这随笔主要目的是方便自己以后使用，当然很是欢迎大...
[BZOJ1226][SDOI2009][状态压缩DP]学校食堂Dining
<题目> 小F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，...
POJ 2441 Arrange the Bulls 状态压缩递推简单题 （状态压缩DP）
推荐网址，下面是别人的解题报告：http://www.cnblogs.com/chasetheexcellence/archive/2012/04/16/poj2441.html里面有状态压缩论文的链接，可以看看。该解题报告中用的是二维数组，但是很显然的是，递推式中的下一行只与上一行有关，类似于最长...
POJ 1185 状态压缩DP（转）
1. 为何状态压缩：棋盘规模为n*m，且m≤10，如果用一个int表示一行上棋子的状态，足以表示m≤10所要求的范围。故想到用int s[num]。至于开多大的数组，可以自己用DFS搜索试试看；也可以遍历0~2^m-1，对每个数值的二进制表示进行检查；也可以用数学方法（？）2. 如何构造状态：当然，...
HDU4539+状态压缩DP
/* 题意：n行m列的矩阵，1表示可以放东西，0表示不可以。曼哈顿距离为2的两个位置最多只能有一个位置放东西。 问最多放多少个东西。 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #incl...
状压dp（状态压缩&&dp结合）学习笔记（持续更新）
嗯，作为一只蒟蒻，今天再次学习了状压dp（学习借鉴的博客）但是，依旧懵逼··································这篇学习笔记是我个人对于状压dp的理解，如果有什么不对的地方，希望大家指出。闲话不多说，进入正题。首先，在介绍状压dp之前，我们先来了解一下状态压缩（常用的为二...
hdu 5025 Saving Tang Monk 状态压缩dp+广搜
作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092939.html题目链接：hdu 5025 Saving Tang Monk 状态压缩dp+广搜使用dp[x][y][key][s]来记录孙悟空的坐标(x,y)、当前获取到的钥匙key和打...