高度由习惯堆积

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

CSP模拟赛 巨神兵

题目欧贝利斯克的巨神兵很喜欢有向图,有一天他找到了一张$n$个点$m$条边的有向图。欧贝利斯克认为一个没有环的有向图是优美的,请问这张图有多少个子图(即选定一个边集)是优美的?答案对$10^9+7$取模。对于40%的数据$n≤5,m≤20$对于60%的数据$n≤10$;对于80%的数据$n≤15$;对于100%的数据$n≤17$。思路考场上只会写枚举边集的纯暴力,后来发现自己蠢爆了。首先这题...
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...