[笔记]状压DP


状压dp状压dp适用于只有两种状态(放/不放)

二进制状态数在20位内
二进制运算

& 与   同1则1

| 或   单1则1

^ 异或 不同则

1 << 左移 eg.二进制下 0001<<2=0100

> 右移

状压二进制操作

判断二进制数x的第j位是否为1 if(x&(1<<j))

在二进制数x的第j位+1 x|(1<<j)

去掉二进制数x最后一个1 x&(x-1)
例题1

当前行摆法仅对下一行可能产生影响 考虑m+1行全空 即为m行全满 边界 dp[1][0]=1第1行不填有一种 dp[i][state] 第i行在第i-1行填完后的状态state 为方便反存 dp[m+1][0]即为答案

例题2

dp[i][state] 当前第i个 已经穿过的状态为state dp[转移后][转移后状态]=min(dp[转移后][转移后状态],d[转移前][转移后]+dp[转移前][转移前状态]) max(dp[i][(1<<n)-1])即为答案


年轻即追梦!