高度由习惯堆积

分类 算法:状压dp 下的文章

February 17, 2019

HDU5555 Immortality of Frog

题目N frogs are attempting to prolong their life-span. They live in the bottom of a well which can be described as a two-dimensional N×N grid. Grid(i,j) is located in the i−th row and the j−th colum...
February 17, 2019

HDU4281 Judges's response

题目已知 n 个点的坐标,裁判在 1 号点。2-n 号上有人提问,需要过去回答。每个人的问题需要的解答时间为 Ci,每个裁判回答问题的总时间不能超过 m.求:1:最少需要的裁判数量2:如果裁判数量无限,最少在路上的时间是多少?思路这题当初写着貌似比较卡,但这也是状压中比较常见的一种题型。对于问题1而言,我们可以状压回答问题的情况,来枚举其需要的裁判数量,比较简单。这里我使用$sta[j]$来...
February 17, 2019

HDU4114 Disney's FastPass

题目一个图 ,有 n个点 ,有 m条边 ,有 k个点是你要参观的(需排队 ,花时间 t),然后你到某点时 ,可能以获 得一种加速票 ,这种票可以让你在 i点时排队只需花 ti 的时间 .求参观完这 k个点所需最少时间 .思路到达了一个点之后,我们显然要将这个点的票全部取得,于是我们可以开$dp[i][j][k]$表示到了哪个点,取得了哪些加速票,以及参观了哪些需要参观的点。这样先Floyd求...
February 17, 2019

HDU1400 Mondriaan's Dream

题目用12的矩形填满n m的方格,求方案数。思路由于是状压的专题,所以很自然的想到状压,我们可以这样编码,对于是竖着的,且会影响下一层的方块,我们使用1将其标记,其余使用0exam:对于样例第一层:00100001100.这样本层对应的二进制数j与上一层的k之间就不能在同样的位子上是1。且j^k的值所产生的0,其对应的位置就是本层的横放的格子。所以连续的0格子必须是偶数。代码#includ...
February 16, 2019

Topcoder9902 SRM416 DancingCouples

$dp[i][S]$表示选到某个男生,女生的选择集合。然后暴力转移,复杂度$O(2^{n*m}*K*m)$极限数据一亿多,然而卡过去了。#include<bits/stdc++.h> #define clr(x,y) memset(x,y,sizeof(x)) using namespace std; int n,m,ans=0; bool A[15][15]; vector&l...