好學易懂從零開始的插頭DP（一）

2020 年 11 月 22 日
筆記
動態規劃, 模塊總結

好學易懂從零開始的插頭DP（一）

寫在前面

這是一篇，以蒟蒻視角展開的梳理總結。更改了一些順序，變化了一些細節。方便蒟蒻學習理解（起碼本蒟蒻是這樣）。大佬們可以直接看其它大佬的博客，可以學的更快。

你必須要學會的前置知識：狀態壓縮DP
學不會依舊可以讀，但是推薦學的前置知識：哈希

什麼是插頭DP

很顯然，是一個關於插頭的動態規劃。那麼，什麼是插頭呢？

如圖我們在一個方格內，關於格點畫一條閉合迴路。

對於每一個方格，內部，有六種情況

不難發現，對於迴路里的任何一個方格，四條邊中，有且僅有兩個與表示路徑的藍色線相交。這也很好理解，進一次，出一次，C（4，2）=6。
我們現在把格子里的藍色線條，變成從格子中心指向外邊的→。

這個箭頭，也就是所謂的插頭。

例題

我們結合一個例題來看，這個題目是洛谷模板題的弱化版，很多博客放在了模板題後的第一題，結合個人經歷我覺得它比模板題更適合作第一題。
題目鏈接：HDU1693 or 洛谷P5074
題目大意：給一個n*m的方格，有些格子必須走，有些格子不能走。問有多少種不同的閉合迴路。（1<=n,m<=12)

那麼，把迴路模型變成插頭模型有什麼好處或者性質呢？
1：首先，我們可以發現，如果一個格子上方的格子有下插頭，那這個格子一定有上插頭。其它方向類似。
2：一個格子的合理取法合且僅合相鄰的格子有關。

觀察下第二點，它其實代表了無後效性。假設我們從上到下，從左到右的處理每一個格子，那麼我們只需要記錄部分格子的狀態即可，再往上的格子具體狀態不用知道。

如上圖，對於當前格子，我們只需要知道紅色的這些格子就行了，再上面的格子具體的取法，已經不會對下面任何未處理的格子產生影響。

已經掌握了狀態壓縮的你，一定能輕鬆的算出狀態總數，每個格子6種，維護n個格子。總共 $6^n6n種狀態，好的，完蛋，只有2e9個狀態。<img alt="在這裡插入圖片描述" src="//img-blog.csdnimg.cn/20201122224203516.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbGx5aWR5bGxpYw==,size_1,color_FFFFFF,t_70#pic_center" style=""/>別急，我們真的需要2e9個狀態嘛？這些格子里，指向彼此和已經處理過的格子的插頭，顯然是廢物信息。我們實際上只需要知道這些插頭嘛：<img alt="在這裡插入圖片描述" src="//img-blog.csdnimg.cn/20201122224509979.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbGx5aWR5bGxpYw==,size_16,color_FFFFFF,t_70#pic_center" style=""/>藍色的是其它格子需要用到的，黃色的是當前格子需要用到的。我們只需要知道這m+1個箭頭是否存在就可以了。總共2 m ∗ 2 2^m*22m∗2個狀態。再乘上n和m，時空複雜度都綽綽有餘。那麼，怎麼實現呢？我們要解決兩個問題。$

1：已知這些插頭的情況下，這個方格該如何填。
2：填完這個方格後，如何得到下一個方格所需要的插頭狀態，更特殊的，如何從上一行行末，變到下一行行初。

這兩個問題，其實都不是很難，稍微思考下，都可以獨立解答，建議思考後再往下看。圖片擋下文大法。

問題1：
1：如果當前格子存在左側插頭和上方插頭，那麼只有一種合理填法。

2：如果僅存在左側插頭，那麼有兩種合理填法。

3：如果僅存在上方插頭，那和上一種類似，也是兩種填法。

4：如果都不存在呢？只有一種填法

問題2：
解答了問題1，顯然我們也得到了問題2的解答，畢竟我們填出了這個格子，自然知道插頭分佈。唯一特殊的是上一行末到這一行頭的處理。上一行末不可能有右插頭，那我們直接把上一行末狀態的表示最後是否存在右插頭的位置去掉，再添加一個表示沒有左插頭的位，不就表示出了這一行第一個的狀態了嘛，為了方便寫，下方的代碼里，我用dp[i][0][mask]表示轉移後的上一行行末狀態。

到這裡，我們已經得到了解法了，成熟的評測機，應該自動AC了吧（划去）。插頭DP還是要多寫的，千萬自己寫一遍，別忘了，這只是模板題的弱化。
這裡提供一份代碼（洛谷AC）

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m,maxk,a[13][13];
 6 long long dp[13][13][1<<14];
 7 void init()
 8 { 
 9     scanf("%d%d",&n,&m);
10     maxk=(1<<(m+1))-1;
11     for (int i=1;i<=n;i++)
12     {
13         for (int j=1;j<=m;j++)
14         {
15             scanf("%d",&a[i][j]);
16         }
17     }
18     memset(dp,0,sizeof(dp));
19 }
20 void solve()
21 {
22     int prei,prej;
23     dp[0][m][0]=1;
24     for (int i=1;i<=n;i++)
25     {
26         for (int k=0;k<=maxk;k++)
27         {
28             dp[i][0][k<<1]=dp[i-1][m][k];
29         }
30         for (int j=1;j<=m;j++)
31         {
32             prei=i;
33             prej=j-1;
34             for (int k=0;k<=maxk;k++)
35             {
36                 int b1=(k>>(j-1))&1;
37                 int b2=(k>>j)&1;
38                 if (!a[i][j])
39                 {
40                     if (!b1&&!b2) dp[i][j][k]+=dp[prei][prej][k];
41                 }
42                 else if (!b1&&!b2)
43                 {
44                     dp[i][j][k+(1<<j)+(1<<(j-1))]+=dp[prei][prej][k];
45                 }
46                 else if (b1&&!b2)
47                 {
48                     dp[i][j][k]+=dp[prei][prej][k];
49                     dp[i][j][k+(1<<(j-1))]+=dp[prei][prej][k];
50                 }
51                 else if (!b1&&b2)
52                 {
53                     dp[i][j][k]+=dp[prei][prej][k];
54                     dp[i][j][k-(1<<(j-1))]+=dp[prei][prej][k];
55                 }
56                 else if (b1&&b2)
57                 {
58                     dp[i][j][k-(1<<j)-(1<<(j-1))]+=dp[prei][prej][k];
59                 }
60             }
61         }
62     }
63     printf("%lld\n",dp[n][m][0]);
64 }
65 int main()
66 {
67     int t;
68     scanf("%d",&t);
69     while (t--)
70     {
71         init();
72         solve();
73     }
74     return 0;
75 }

View Code of P5074

電腦前這個努力的帥氣身影是誰呢？そう私です

Tags: 動態規劃模塊總結