zcmimi's blog

arrow_back状压dp共16篇文章

avatar
zc
2020-10-19 21:49:55

查看原题

点击跳转

f[sta]为死了的猪状态为sta时最少需要多少鸟

f[sta|line(i,j)]=\min(f[sta]+1)(line(i,j)表示经过i,j的抛物线能杀死的🐖的集合)

f[sta|(1<<i)]=\min(f[sta]+1)

优化:

若令x为满足sta\&(1<<(x-1))=0的最小正整数,则由sta扩展的转移的所有线都要经过x

avatar
zc
2020-10-17 11:25:38

查看原题

点击跳转

x构造一个矩阵满足a(i,j+1)=2a(i,j),a(i+1,j)=3a(i,j)

对于这个矩阵,我们不能选相邻的数,也就是说答案为不选相邻的数的方案数

这个矩阵长\log_2 n(不超过17),宽\log_3 n(不超过12),因此可以用状压dp解决

我们只需要对不是2,3倍数的数都构造一个矩阵就可以覆盖所有的数,容易发现每个矩阵互不相同,所以根据乘法原理把答案相乘即可

avatar
zc
2020-05-05 09:31:00
查看原题

点击跳转

f(i,j,0/1,0/1)表示第i轮的第j场,你是否是胜利者的粉丝,是否是失败者的粉丝

可以发现轮数有点像堆,如果轮数从0开始编号,第i轮的第j场由第i-1轮的第2j场、第i-1轮的第2j+1场转移而来

avatar
zc
2020-04-26 16:20:00
查看原题

点击跳转

f_{i,j}表示前i个点,第i个点的覆盖状态为j(j8位二进制数)

avatar
zc
2020-01-19 10:55:00
查看原题

点击跳转

f[sta]表示sta表示的所有颜色都排列到从1开始的相连的一段,最少要多少次

pre[i][j]表示所有颜色i前面总共有多少个颜色j,也就是说要将所有颜色i移动到颜色j左边要移动多少次

即:\sum[y<x,c[x]=i,c[y]=j]

sta[i]表示sta表示的第i种颜色的状态

f[sta]=\min{f[sta']+\sum_{sta[j]=1,sta[k]=0}pre[j][k]}

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

可以看到n\le 15,我们很容易想到状压

状压解法:

f[i][j]表示到了第i位,匹配的状态为j

代码:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[st][sta]表示起点是st,当前节点是否访问过的状态二进制下是sta

顺便记录d[st][sta]表示f[st][sta]最小时每个节点距离st的距离

我们可以用填表法向前推进

f[st][sta'] = \min(f[st][sta'],f[st][sta]+(d[st][sta][x]+1)\times L) (sta' = sta | 2^{to-1})

最坏情况下复杂度: \Theta(n \times 2^n \times n^2)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[x]表示状态为x时最少走多少步

枚举现在取哪两个点,然后

f[x|2^{i-1}|2^{j-1}]=\min(f[x|2^{i-1}|2^{j-1}],f[x])

如果直接枚举不剪枝的话可能会TLE

所以我们只要找到第一位是1的,然后往后面枚举就可以了,因为不关怎么样我们都要把全部取完,先取后取是一样的

(如果不懂可以自己模拟一下)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以把每一行的SG异或

每一行只有20个,所以可以用状态压缩

可以通过动态规划或记忆化搜索的方式处理出每种状态的SG

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

1/2
Search
search