狀壓dp

視頻鏈接
（如果想購買網課，可以用我的邀請碼）
用我的鏈接購買，我再反你10，一共花54多值
購買鏈接
不放心可以先加我好友2830872914

總試題鏈接

文章目錄

• • 狀壓dp
  • 預備知識——位運算
• 例題：
• • 引入：
  • NC20240 [SCOI2005]互不侵犯
  • NC16886 炮兵陣地
  • TSP問題 NC16122郊區春游 NC16544簡單環
  • NC15832 Most Powerful
  • 棋盤覆蓋 poj2411 NC107008 Mondriaan's Dream
  • 總結：
• 習題：
• • NC14732 鎖
  • NC15034 德瑪西亞萬歲
  • NC16418 寶藏
  • NC17061 多彩的樹
  • NC17890 方格填色
  • NC20485 [ZJOI2009]多米諾骨牌

預備知識——位運算

當做01串處理
<< 左移（有可能溢出）
.>> 右移（最后一位丟掉）
| 或
& 和
^ 異或（相同為0，不同為1）
~ 取反
操作：
去掉最后一位：x>>1
在最后加上一個0：x<<1
在最后加一個1：（x<<1）+1
把最后一位變成1：x | 1
把最后一位變成0：（x|1）-1
最后一位取反：x^1
把從右邊數第k位變成1：x | (1<<(k-1))
把從右邊數第k位變成0：x&（~（1<<(k-1)））
把右數第k位取反：x^(1<<(k-1))
取末k位：x&((1<<k)-1）
取右數第k位（x>>(k-1)）&1
把末k位變成1:x|((1<<k)-1)
末k位取反:x^((1<<k)-1)
把右邊連續的1變成0: x&(x+1)
把右邊第一個0變成1: x|(x+1)
把右邊連續的0變成1： x|(x-1)
去右邊連續的1：(x^(x+1))>>1
去掉右邊第一個1的左邊：x&(-x)

例題：

引入：

在n*n的方格上放n個車，它們不能在同一行列，問總方案數
方法：階乘 n！

添加要求：某些格子不能放
方法：
取棋子的放置情況當做狀態，放則為1，不放為0
n=5，第1,3，4已經放置，狀態就是01101（從右向左）
dp[i][st]表示前i行的狀態為st的方法數
dp[i][st]=∑dp[i-1][st’]
st理解成01串
st’與st關系滿足：(st’ & (1<<(j-1)))==0 && st’ +(1<<(j-1)) = = st
st’中第j列沒有放，并且st’放上第j列后就等于st
st’=0 0 1 0 1
然后放在第四列
st=0 1 1 0 1

NC20240 [SCOI2005]互不侵犯

題解鏈接
題目：n*n的方格放k個車，車之間不能靠著，問多少種方法？
題解：
需要知道前一行的情況，所以一行一行的放車
記錄每行的情況
在本題中，不能存在相鄰的1
對于一行x：
(x&(x<<1))==0----->可以判斷左右是否有相鄰的1
對于上一行x，下一行y：
(x&y）= = 0
(x&(y<<1)) = =0
(x&(y>>1)) = = 0
上下，左下，右下都不為0
dp[i][j][k]表示第i行狀態為k，已經放了j個車
轉移方程：
dp[i][j][k]+=dp[i-1][j-num[k]][p]
(k&p) = = 0
(x&(p<<1))= =0
(x&(p>>1))= =0
num[k]表示k狀態的國王數

NC16886 炮兵陣地

題解鏈接
題目：
n*m個網格，有平原，有山地，平原可以放部隊，部隊攻擊范圍如圖（不受地形影響）

在防止誤傷的情況下，最多能放多少炮兵部隊
題解：
確定狀態：
因為每個炮可以打到兩行，所以每一行放置方式與他放置的情況有關
dp[i][j][k]表示第i行為狀態j，第i-1行為狀態k時所用的最大炮兵數
也就是同時記錄兩行狀態，根據已知的兩行狀態推下一行
狀態轉移：
dp[i][j][p]=max(dp[i][j][p],dp[i-1][p][q]+num[j])
q被枚舉
第i行狀態：j
第i-1行狀態：p
第i-2行狀態：q
j，p，q不能發生沖突
任意1左右兩邊兩位都不是1
((i&(i>>1))==0) && ((i&(i>>2)) ==0)
且1的位置必須是平原
優化：保存符合條件的二進制串，只枚舉自身符合要求的二進制串

TSP問題 NC16122郊區春游 NC16544簡單環

郊區春游題解鏈接
簡單環題解鏈接
題目：
給定一張圖，求從某個起點出發，經過所有的點的最短路徑（每個點經過且只經過一遍）
題解：
dp[st][i]表示當前狀態st，最后到達的一個點是i，所經過的最短路徑
st是01串，1表示該點走過
狀態轉移：
dp[st][i]=minn(dp[st’][j]+a[j][i])
st’+(1<<(i-1))==st
st’&(1<<(i-1))==0
st’第i位是0
st第i位是1
擴展
如果要求走完所有的點回到原點怎么辦？
dp[111111][？？]
？？：1—>n
加上1到起點的距離，2到起點的距離…，比較哪個最佳

NC15832 Most Powerful

題解鏈接
題目：
不超過十種氣體，兩兩碰撞產生一定能量，a碰b，b就會消失，不能自身碰，問最后得到的最大能量
題解：
確定狀態：
dp[i]表示狀態i時所能獲得的最大能量
i的第k位為1，則說明第k個氣體已經用了并消失。為0則說明沒用或是用了沒消失
狀態轉移：
dp[k|(1<<(i-1))]=max(dp[k]+a[j][i])]
用當前狀態k推出新狀態（狀態是往前看）
k|(1<<(i-1))：k的第i位變為1，第i個氣體沒了
i和j均要枚舉

答案dp[x]:x為只有一個0的01串

棋盤覆蓋 poj2411 NC107008 Mondriaan’s Dream

題解鏈接
題目：
n * m的矩陣，用1 * 2和2 * 1的磚快密鋪，問多少種方法：


豎向磚塊我們上面填0，下面填1
上下兩行狀態做&操作，為0的位置就是豎向磚塊的下邊沿，剩下的1就是下邊磚塊的，相鄰的1是否為偶數個，如果是偶數個說明可以填滿，否則不合理
（太難了~ ~ ~）

總結：

把復雜的情況壓縮，將一個狀態壓縮成一個整體
hash過程
什么問題用狀壓dp：
在棋盤格子上覆蓋，有一維不是很大即可
類似于TSP的路徑問題
N比較小，變成n位二進制后還很合理

習題：

題目鏈接

NC14732 鎖

NC15034 德瑪西亞萬歲

NC16418 寶藏

NC17061 多彩的樹

NC17890 方格填色

NC20485 [ZJOI2009]多米諾骨牌

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客网状压dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。