夢に僕らで帆を張って
来るべき日のために夜を超え

标签 状态压缩 下的文章

October 24, 2019

洛谷P3067/USACO12OPEN 平衡的奶牛群Balanced Cow Subsets

题意给出$n$个数,从中选出一些,求选出的数能分成相等的两份的方案数数据范围:$2 \le n \le 20$题解对于每个元素,无非$3$种状态:$0$ 不选$-1$ 左$1$ 右但直接搜索复杂度达到$O(3^n)$考虑折半搜索将组合二进制压缩,前半搜索记录下可能的$sum$,后半搜索从前半中找到相等的$sum$(其实是找$-sum$,但是是等价的),则此种选择方案成立由于$sum$较大,需...
October 12, 2019

洛谷P4163/SCOI2007 排列

题意给一个数字串$s$和正整数$d$, 统计$s$有多少种不同的排列能被$d$整除数据范围:$s$的长度$\le 10,1 \le d \le 1000$题解直接计算整除的较为麻烦,可以状压使用过的数$d$并记录当前数模$d$的余数,再来表示方案数用$f[i][j]$表示选用过的数状态压缩为$i$,当前余数为$j$易得状态转移方程$$f[i|(1<<j)][(k*10+a[j])...
September 26, 2019

洛谷P2704/NOI2001 炮兵阵地

题意:司令部的将军们打算在 $N \times M$ 的网格地图上部署他们的炮兵部队。一个 $N \times M$ 的地图由 $N$ 行 $M$ 列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示:如果在地图中的灰色所标识的平原上部署...
September 26, 2019

洛谷P2157/SDOI2009 学校食堂

题意略数据范围:$1 \le N \le 1,000,0 \le T_i \le 1,000,0 \le B_i \le 7,1 \le C \le 5$题解因为可以将后面的提前,影响了后效性,需要额外保存后$B_i$个人的状态,注意到$0 \le B_i \le 7$,考虑使用状压用$f[i][j][k]$表示考虑到第$i$个人,状压保存的其后$B_i$个人的状态为$j$(对应位上$0$表...
September 26, 2019

洛谷P1896/SCOI2005 互不侵犯

题意:在 $ N×N $ 的棋盘里面放 $ K $ 个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共 $ 8 $ 个格子。数据范围: $ 1 \le N \le 9,0 \le K \le N * N $题解:算法:状压dp使用 $stt[]$ 记录每一种状态,二进制下从低位到高位记录此行从左到右是否放置国王。并且由于有...
September 26, 2019

CF1209E Rotate Columns

题意给出一个矩阵,可以选择一个列循环移位,求每一行的最大值的最大和数据范围:$1 \le n \le 12,1 \le m \le 2000$题解我们可以记录每一列的选择情况,容易想到这是状压$dp$用$dp[i][j]$表示前$i$列的选择情况为$j$的和,其中$j$的第$k$位表示选择第$k$行但是由于$m$较大,这样会太慢我们可以按每一列的最大值对列从大到小排序,容易证明,只会选择前$...