menu zcmimi's blog

arrow_back 状态压缩

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

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

zc
2020-01-19 10:55

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47

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

状压解法:

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

代码: ```cpp

include<bits/stdc++.h

zc
2019-12-21 19:47

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想

zc
2019-12-21 19:47

f[0] = 0 

i指状态压缩后的二进制数)f[i]=\sum f[i']) 

lowbit可以很快地获取一个数在二进制下第一个1在哪 

一直lowbit和异或就可以把所有1找到

zc
2019-12-21 19:47

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

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

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

```cpp

include<bits/stdc++.h>

zc
2019-12-21 19:47

f[i][sta]表示以第i只奶牛结尾,状态为sta的情况下有多少种

f[i][sta] = \sum f[i-1][sta'] ```cpp

include<bits/stdc

zc
2019-12-21 19:47

看了看数据范围,可以知道是状态压缩+区间dp

我们设f[i][j][t]表示[i,j]合并后状态为t获得的分数

$f[i][j][t] = f[i][k][t'] + f[k+1][j

zc
2019-12-21 19:47

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

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

我们可以用

zc
2019-12-21 19:47

题意

一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。

zc
2019-12-21 19:47
1 / 2
Search
search