UESTC 891 Diagrams & Tableaux(状压dp?,NERC2013)

9-01 664 views

题意:对于任意一个位置的数,他的右边大于等于他,他的下面的数大于他,问有多少种组合满足题意。 思路: 1.比赛的时候一直以为复杂度不够不够过不了,没敢...
阅读全文 0

HDU 5117 Fluorescent(状压dp+数学)

8-31 716 views

题意:有n个灯和m个开关,每个开关控制着一些灯,如果一些开关按下,会有对应的响应(本来亮着现在暗了,反之亦然),问E(X^3)*2^M是多少 思路: 1.       ...
阅读全文 0

HDU 4906 Our happy ending(状压dp)

8-25 731 views

题意:问有多少种序列满足可以选出一些数字,和为k。且每一个数最大为l。 思路:最初设计状态的时候,会有很多重复的计数。也想过状压,但是复杂度太高,高达...
阅读全文 0

ZOJ 3812 We Need Medicine(状态压缩式的01背包)

8-02 586 views

题意:给定n种要药品,有两个属性(x,y), 现在有m种病毒,有两个属性(a,b),问对于任何一个(a,b)是否可以由其中的(x,y)相加得来。对于每一种药品...
阅读全文 0

POJ 2436 Disease Management (二进制枚举子集)

4-08 1,324 views

这个题比较简单。 一看病毒的数量就可以往二进制上思考。 因为最多为 15种病毒, 最多 k 种病毒, 那么我们就选二进制中 1 的个数为 k 的进行查询所有的牛。 ...
阅读全文 0

POJ 2686 Traveling by Stagecoach(状压dp)

3-24 631 views

比较简单的dp。 和之前求最短路的差不多。 用 d【i】【j】 来表示  i中 邮票的集合 还有哪几个邮票还没用, 此时 在 j 城市的最小时间 注:POJ 用 G++编译器 ...
阅读全文 0

福州大学月赛 Problem D 小明的迷宫 (bfs+状压dp)

3-22 613 views

比较好的一个题。 在一个图上 宝藏的个数 k <= 10, 一看这么小的数据 那就可以想到状压 吃完所有宝藏的最短路径。 首先要求出所有宝藏的之间任意两点的最...
阅读全文 0

UVA 11795 – Mega Man’s Mission(状态压缩dp)

12-16 1,128 views

比较简单的dp。 不过自己也搞了好长时间。 问题主要是在对什么进行压缩的问题上。 自己第一遍写的时候。 对当前的武器进行了压缩。  但是后来在压缩的时候。 ...
阅读全文 0
加载更多