HDU 1693 Eat the Trees 插頭DP入門

2019 年 11 月 14 日
筆記

緣起

終於該來的還是得來~ 插頭DP入門學習! HDU 1693 Eat the Trees

分析

給出一張n*m有障礙的棋盤，要求用任意條非平凡哈密頓迴路遍歷整個棋盤，不能經過障礙格子，  要求統計不同的行走方案數。所謂非平凡指的是迴路的長度>1（一個格子也構成一條迴路，但是它長度為1,是平凡的  哈密頓迴路）    【輸入】  多樣例. 第一行是樣例的數目, 對每個樣例，第一行是n和m，1<=N, M<=11，然後下面是n*m的01矩陣  1表示此格子沒有障礙, 0表示此格子有障礙.    【輸出】  對每個樣例輸出方案數. 輸入保證答案不會超出 2^63-1    【樣例輸入】  2  6 3  1 1 1  1 0 1  1 1 1  1 1 1  1 0 1  1 1 1  2 4  1 1 1 1  1 1 1 1    【樣例輸出】  Case 1: There are 3 ways to eat the trees.  Case 2: There are 2 ways to eat the trees.    【限制】  2s

舉個例子 N = 6 and M = 3,灰色的格子表示是障礙，答案是3

關於插頭DP，最早的題目出現於04年，但是論文《基於連通性狀態壓縮的動態規劃問題長沙市雅禮中學陳丹琦》是08年才出現的（神犇女俠 CDQ 救世 or2）. 所以關於插頭DP要看原著的話肯定還是推薦CDQ女神的論文。沒錯, 就是那個發明了 CQD分治、插頭DP的神犇~

首先說清楚, 因為本題也是我插頭DP入門, 而且CDQ的論文也只讀了第一部分. 所以未必吃透了插頭DP. 但是我會用大白話將我對插頭DP的理解說清楚. 幾百年前，大數學家高斯就說過寧可少寫，寧可好些

我不會從什麼是插頭，什麼是輪廓線講起。而是希望能以一個自然的思路引出這些概念. 首先我想講一道《啊哈!算法》4.6節的一道題目.

《水管工遊戲》

給你一塊土地，土地被分割成N*M的棋盤. 一些單元格下面埋藏有一根水管。水管的形狀只有直的和彎的兩種

現在你的任務是旋轉這些水管，使得構成一個管道系統，即創建一條從（1,1）到（n,m）的連通管道。但是市政不能破壞森林。有一些單元格已經種了樹，下面是沒有鋪設管道的。除此之外都是埋有水管的。例如下面這個樣子

我們可以旋轉其中的一些單元格下面的管道使之構成一個連通的管道系統

如果可以通過旋轉管道使之構成一個連通的管道系統，則輸出鋪設的路徑，否則輸出"Impossible"

對於此題，是dfs的入門題——因為每個格子的水管鋪設情況只能是下面6種（其中4種是彎管，一種是直管）

所以只需要根據每個方格的上述6種水管狀態進行擴展即可. 當然，還有一個要素——就是當前方格的進水口到底是位於當前格子的上下左右. 因為進水口的位置顯然限制了能使用哪種水管狀態. 例如，如果進水口在上方，你總不可能用2這種狀態吧? 當前格子只能使用1、4、6三種狀態才行.

所以dfs的偽代碼應該是下面這個樣子

dfs(int x,int y, int dir) // (x,y)是當前要決定水管的格子的行與列,dir是當前格子進水口的方向  {  	if(x==n && y ==m+1) // 如果當前決定狀態的格子已經是(n,m+1)了,則表明已經通了  	{  		puts("找到一組解了!");  		return;  	}  	if(v[x][y] || (x,y)越界了) // v是標記當前格子的水管狀態是否已經決定了  	{  		return;  	}  	v[x][y] = true; // 鎖定  	if(當前格子中鋪設的水管是直管)  	{  		if(dir是上方) // 進水口在上方, 則只能使用水管狀態6  		{  			dfs(x+1,y,上方); // 則拓展到下一行(x+1,y)格子, 而且此格子的進水口也是在上方  		}  		else if (dir是下方)  		{  			dfs(x-1,y, 下方);  		}  		else if (dir是左方)  		{  			dfs(x,y+1,左方);  		}  		else (dir是右方)  		{  			dfs(x, y-1, 右方);  		}  	}  	else // 當前格子中鋪設的水管是彎管  	{  		類似於直管進行拓展...  	}  	v[x][y] = false; // 解除鎖定  }

為什麼說《水管工遊戲》（下面簡稱遊戲）道題目呢? 因為和本題有點像啊~ 本題不就是也給你一個棋盤，然後要求在這個棋盤上生成一些迴路然後將棋盤覆蓋掉嗎? 而遊戲中是水管的狀態構成了通路。而本題呢? 一樣的呀~ 也是每個格子要選擇水管的6種狀態中的一種使得整個棋盤構成一種圖論的狀態! 而水管的6種狀態本質上是由格子的四條邊的選擇2條

構成的（即所謂的雙插頭狀態（下面簡稱插頭狀態）共6種）。而每條邊一旦選了，就叫做這條邊上存在插頭。所以對於本題而言，其實就是每個格子選擇6種雙插頭狀態中的一種然後使得所有格子形成若干條非平凡的哈密頓迴路（我們稱之為成功局面）。一旦達到了成功局面，我們就得到了一種方案. 所以本題其實是dfs,

等等~

數據的規模是11*11, 即100+個格子, 我們要決定每個格子的6種狀態中選哪一種. 所以如果不剪枝的話, 狀態樹的規模達到了

分分鐘炸飛服務器的節奏啊！

不能用暴搜！其實你想想看哈，有必要暴搜嗎? 什麼意思? 下面是一棵樹的樣子

K的狀態其實是怎麼到的? 首先你要達到A, 然後在A處選擇了B，最後在B處選擇了G，最後G選擇了K. 即K這個狀態是直接受到他的所有祖先影響的! 但是對於本題而言. 一個格子的狀態選擇僅僅和所謂的輪廓線上的插頭狀態有關. 所以暴搜是完全沒有必要的——因為一個格子（例如下圖中黃顏色的格子）的插頭狀態不會受到太早做出的插頭狀態選擇的影響，而僅僅會受到輪廓線的影響. 如果做過poj 1185 炮兵陣地（參考【1】）這道經典狀壓DP的童鞋就知道當前排的布陣僅僅受到上一行、上上行的布陣的影響.

說了這麼多, 輪廓線是啥?

假設我們是從上至下、從左至右決策各個格子的插頭狀態.

圖有點丑，見諒哈~ 上圖中粗線 LA、LB、LC、LD 就是輪廓線. AA、BB、CC、DD 是當前決策好的格子. A、B、C、D是下一步要決策的格子. 其中BB和D是虛擬的格子（因為棋盤僅僅是[1,…,n]*[1,..,m] n行,m列的）,BB在第0列, D在第m+1列.

換個角度看輪廓線上方是已經決策完的格子，下方是未決策的格子. 注意決策的決策格子換行是什麼意思? 就是決策完DD之後, 輪廓線就從形如LD變成了形如LB的樣子.

注意, 輪廓線的長度始終是m+1（m個橫着的單位長度，1個豎著的單位長度）.

我們考察一下最終合法方案造成這條長為m+1的輪廓線上插頭是否存在的情況.

例如上面n = 5, m = 6 地圖中的粗黑線就是一條哈密頓迴路（而且上圖給的例子中地圖中沒有障礙物）遍歷了地圖全部的格子. L1和L2是兩條輪廓線. 顯然上圖就是一種合法的最終方案. 如果將出現插頭記做1, 沒有出現插頭記做0的話, 則一條輪廓線就可以用一個長度為m+1的01序列刻畫. 例如 L1是 1111000，而L2是1101111. 所以我們可以對每條輪廓線的狀態二進制壓縮成一個的整數值. 下面有時候說輪廓線L其實是在說L對應的二級制壓縮值.

因為本題m較小, 所以我們完全可以對輪廓線的01狀態（所以確切講, 輪廓線其實是帶着0和1的長度為m+1的序列）進行狀壓DP. 即我們狀壓的對象是輪廓線. 因為下一個格子的插頭狀態完全可以從當前輪廓線進行轉移. 而和之前較早決策的格子的插頭狀態無關. 所以不需要暴搜. 而是狀壓DP就行了。這將大大降低算法的複雜度.

下面給出本題DP的對象

令dp[i][j][k] 是當前已經決策完 第i行, 第j列的格子（1<=i<=n, 1<=j<=m）,輪廓線狀態是k時的方案數.  0<=k<(1<<(m+1)). 為什麼是m+1? 因為說了啦, 輪廓線是長度為m+1的01序列啦~  ps: 這裡插一句, 這裡的DP對象其實和【1】好像的說~  dp的初始值是 dp[1][0][0] = 1  即第一行第0列決策完, 輪廓線狀態是0（事實上, 輪廓線狀態只能是0啊~）的方案數就是1.  答案是 dp[n][m][0], 即決策完全部的格子, 輪廓線的狀態是0  （決策完最後一個格子輪廓線的樣子是形如LD樣子,只不過LD在棋盤最底部邊線, 所以自然輪廓線狀態是0啦）

那麼說完了dp的東西以及初始化還有最終答案，那麼我們自然要考慮的重點就是狀態轉移了. 因為是狀壓DP（ps: 因為本題是針對輪廓線的狀態進行狀壓，而且涉及到的輪廓線本質上還是由插頭這一重要的概念引進的. 所以本題所涉及的DP又叫做插頭DP或者叫輪廓線DP, 通過本題你也知道, 插頭DP也好，輪廓線DP也好, 本質上是狀壓DP的一種類型而已，應用場景常見於棋盤這種數學模型）.

所謂狀壓DP就是 F(狀態) = 狀態的值這種東西。所以自然的, 我們要考察兩件事情

從格子 (i, j-1)變到 (i,j) （注意，我們是從左至右、從上至下決策各個格子的）.

狀態怎麼變? 即自變量怎麼變? 更確切講決策完(i,j-1)格子（例如AA）之後的輪廓線和決策完(i,j)（例如A）的輪廓線怎麼變化? 當然, 對於決策發生換行的時候（例如形如LD的輪廓線變動到形如LB的輪廓線）後面作為特殊情況論述, 這裡僅僅將一般的情況說清楚. 對應的狀態的值怎麼變? 即因變量怎麼變? 第一個問題，什麼是狀態? 狀態不就是輪廓線嗎? 前面也說了，輪廓線確切講是輪廓線上插頭的存在情況構成的m+1長度的01序列，1表示存在插頭, 0表示不存在插頭。

狀態的轉移分成下面3種情況

情況1

下圖灰色格子是障礙（下同）

當前決策完畢的格子（即正方形BGDC）在上一次決策完畢（即決策完正方形ABCH（即格子(i,j-1)）產生的輪廓線L1=A->B->C->D->E->F 中沒有左插頭，也沒有上插頭（即BC和CD上都沒有插頭）. 注意, 這種有無插頭是由L1對應的二進制壓縮值值決定的（其實反過來說, 輪廓線上的插頭有無也決定了哈密頓迴路到底長什麼樣子）. 例如對於下圖, L1對應的壓縮值的第1、2個比特位如果是1的話, 則就表示BC和CD兩條邊上有插頭. 因為BC和CD就是L1的第1個、第二個比特位.

上一次決策完畢的正方形ABCH（即格子 (i, j-1)）決策完畢之後, 輪廓線是L1=A->B->C->D->E->F, 而當前決策完正方形BGDC（即格子(i,j)）之後，輪廓線是L2=A->B->G->D->E->F , 因為我們要遍歷全圖. 而且每個格子一定是恰好有2個插頭（一進一出）. 所以這種情況只可能是由L1中BC、CD無插頭變為L2中 BG、DG 有插頭，而且L1、L2中的m+1個位置的01狀態只有這兩個位置不同（0變成了1）其他位置的01情況是相同的. 而且注意, BC、CD在這m+1個01中的排序索引和BG、GD在m+1個01中排序索引是一樣的. 所以就知道L1的對應的二進制壓縮狀態值在O(1)時間就可以得到L2對應的二進制壓縮狀態值。確切講是L1 = L2(1<<j-1)(1<<j) 至於因變量的變化, 自然有 dp(i,j,L1) = dp(i,j-1,L2).

情況2

當前決策完畢的格子（即格子(i,j)，亦即下面的正方形CGED）在上一次決策完畢產生的輪廓線 A->B->C->D->E->F中既有左插頭，又有上插頭，亦即CD和DE上都有插頭.

上一次決策完畢正方形BCDH（即格子(i,j-1)）之後輪廓線變成 L1=A->B->C->D->E->F , 然後當前決策的格子是正方形CGED （即格子(i,j)），當前決策完畢之後，輪廓線變成L2=A->B->C->G->E->F

這種情況下, 假設CD和DE是L1的第j-1和第j個比特位(m>=j>=1)（注意, 輪廓線由m+1個單位長度構成, 所以它有第0個比特位，第一個比特位，第二個比特位,…,第m個比特位構成）則L2對應的二進制壓縮值就是把第j-1個比特位和第j個比特位都由1變成0（即上圖中CG和GE邊上都沒有插頭了）而已.

所以從L1出發O(1)時間就可以得到L2的狀態. 確切講是L1 = L2(1<<j-1)(1<<j) ，而且關於因變量的變化，自然有 dp(i,j,L2) = dp(i,j-1,L1)

情況3

當前決策完畢的格子（即格子(i,j)，亦即下面的正方形BCED）在上一次決策完畢產生的輪廓線 A->B->D->E->F->G中左插頭，上插頭中只有一個，即下圖中 BD、DE中只有一條邊有插頭. 例如下圖是DE存在插頭, 而DB邊沒有插頭

上一次決策完畢正方形ABDH（即格子(i,j-1)）之後輪廓線變成 L1=A->B->D->E->F->G , 然後當前決策的格子是正方形BCED （即格子(i,j)），當前決策完畢之後，輪廓線變成L2=A->B->C->E->F->G

這種情況下, L1和L2的值是相等的. 注意, 此時，我們是讓CE有了插頭（即為1），而BC是沒有插頭的，而且如果DE在L1中是第i個比特位的話, 則CE在L2中也是第i個比特位. 所以我們才說L1和L2的值是一樣的.

如果不是讓CE有插頭, 而是讓BC有插頭呢? 即輪廓線的狀態變成下面的樣子（因為題目並沒有強調必須要一條迴路, 所以下圖也是可以的）

則L2的值和L1的值關係如何呢? 令BD和DE分別是L1的第j-1個比特位和第j個比特位的話(1<=j<=m), 則L1的第j-1個比特位是0, 第j個比特位是1, 則可以知道L2的第j-1個比特位（即BC）將變為為1（即BC將有插頭），第j個比特位為（即CE）0（即CE將沒有插頭）. 即和(i,j-1)格子的時候是反過來了，為什麼說是反過來了? 因為L1的第j-1個比特位是0，第j個比特位是1, 而L2的第j-1個比特位是1, 第j個比特位是0. 所以才說剛好反過來了.

那麼既然我們知道了決策完畢當前格子BCED之後輪廓線對應的值的變化——兩種, 第一種是圖3（不變化），第二種是圖4（兩個比特位反過來）, 所以就知道了 dp(i,j,L2) = dp(i,j-1,L2)+dp(i,j-1,L2(1<<y-1)(1<<y)), 其中 L2(1<<y-1)(1<<y)就表示第y-1個比特位和第y個比特位和L2是反過來了.

最後我們要提及一下換行的情況下輪廓線壓縮的二進制值的變化以及因變量的變化. 前面也已經說過了, 本題中換行其實就是形如LD的輪廓線變成了形如LB的輪廓線。即如下圖所示

即從決策完A格子之後的輪廓線L1變化到決策完B格子之後的輪廓線L2. 那麼我們分析一下L1和L2的值的關係. 顯然, L1的最後那個比特位（豎著的黃線）是0, 而L2的第0個比特位（豎著的藍線）是0. 而其他比特位同為0或者1，所以L2的二進制壓縮值恰好是L1的二進制壓縮值的2倍. 即L2=L1<<1. 則有 dp(i+1,0,L2) =dp(i,m,L1)

而因為L1最後一個比特位是0, 所以0<=L1<(1<<m). 這樣我們就分析完了行轉換時的狀態轉移以及dp公式.

ps: 上面分別進行了逐格（所謂的逐格，指的是決策完畢每一行的第1列的格子到這一行的第m列的格子）的DP（圖1~圖4）以及換行時的DP（圖5），其實就是CQD的論文第一部分中說的逐格遞推和逐行遞推.

作為分析的最後，我們要來講一下遇到是障礙物的時候該如何處理. 例如我們遇到了一隻可愛的障礙物格子

如上圖所示, ABCD是一個障礙物. 則我們考慮和上面一樣的問題——既決策完畢ABCD之後，輪廓線的變化以及以此輪廓線為自變量的因變量的值的變化. 因為ABCD是障礙物, 所以我們要求此格子的四周都不能有插頭. 所以對於L1=E->A->D->C->G->H 和決策完畢ABCD之後的 L2= E->A->B->C->G->H, 首先令 L1=L2, 則意味着AB、BC的比特位情況分別和AD、DC的比特位情況是一樣的. 然後要求AD、DC的比特位皆為0, 則就知道ABCD的四周比特位都是0了. 即「L1的AD、DC為0 && L2==L1」 , 則dp(i,j,L2)=dp(i,j-1,L1)，除此之外的所有情形, dp(i,j,L2)=0, 這就是下面代碼的24行到31行的邏輯. 注意哦~ 可能有認真閱讀的同學會覺得和正常格子的代碼有點不一樣, 因為正常格子的轉移代碼是用(i,j-1)格子的狀態k得到(i,j)格子的狀態k1, 然後是dp(i,j,k1)+=dp(i,j-1,k) （見下面的代碼15-20行）, 而對於障礙格子, 對於不符合AD、BC為0的(i,j-1)格子時的輪廓線k, 我直接讓(i,j)格子時的輪廓線也dp(i,j,k)=0了. 其實如果按照正常格子的風格不應該是dp(i,j,k1)=0嗎(k1是k的變化之後的輪廓線狀態)? 為什麼直接寫成了dp(i,j,k)=0了呢? 其實想想就知道了. 對於使得AD、DC至少一個不為0的輪廓線k, 如果令k為L2的狀態的話, 則就是AB、BC至少一個不為0. 那這樣的輪廓線k1=k顯然是使得dp(i,j,k1)=dp(i,j,k)=0的呀~

至此, 對於本題的各種狀態，我們都得到了dp的轉移方程. 所以可以開心的打代碼了.

//#include "stdafx.h"  #include <stdio.h>  #include <string.h>  //#define LOCAL  typedef long long LL;  LL n,m,a[15][15], bin[15],dp[15][15][(1<<13)+5], full;    void kk(int i, int j)  {  	LL p1 = 1<<j-1, p2 = 1<<j; // 第j-1個比特位和第j個比特位  	for (LL k = 0; k<full; k++) // 注意, k是L1的狀態值,而不是L2的  	{  		if (a[i][j]) // 如果不是障礙物  		{  			dp[i][j][k^p1^p2] += dp[i][j-1][k]; // 圖1、圖2、圖4的情形  			if ((k>>j-1&1)==(k>>j&1))  			{  				continue; // 圖1、圖2、圖4就會continue  			} // 因為只有情形3才要再加上一部分(即圖3).  			dp[i][j][k] += dp[i][j-1][k];  		}  		else // 如果是障礙物（圖6）  		{  			if ((k&p1) || (k&p2)) // AD、DC兩個比特位至少一個不為0  			{  				continue; //  dp[i][j][k]為0  			}  			dp[i][j][k] = dp[i][j-1][k]; // 只有AD、DC兩個比特位皆為0,dp[i][j][k]才可能不為0  		}  	}  }    void sz(int i)  {  	for (int k = 0;k<full>>1; k++)  	{  		dp[i+1][0][k<<1] = dp[i][m][k]; // 圖5  	}  }    int main()  {  #ifdef LOCAL  	freopen("d:data.in", "r", stdin);  	//	freopen("d:my.out", "w", stdout);  #endif  	int kase;  	scanf("%d", &kase);  	for (int kse = 1;kse<=kase;kse++)  	{  		memset(dp,0,sizeof(dp));  		scanf("%lld%lld", &n, &m);  		full = 1<<m+1; // 則輪廓線被狀壓成[0,full)內的一個值  		for (LL i = 1;i<=n;i++)  		{  			for (LL j = 1;j<=m;j++)  			{  				scanf("%d", a[i]+j);  			}  		} // 讀入棋盤  		dp[1][0][0] = 1; // dp初始化  		for (int i = 1;i<=n;i++)  		{  			for (int j = 1;j<=m;j++)  			{  				kk(i,j); // 處理第i行,第j列的格子, 即逐格DP  			}  			if (i<n)  			{  				sz(i); // 換行, 即逐行DP  			}  		} // 開始dp  		printf("Case %d: There are %lld ways to eat the trees.n", kse, dp[n][m][0]);  	}  	return 0;  }

ac情況

Status	Accepted  Time	15ms  Memory	6520kB  Length	1374  Lang	C++  Submitted	2019-11-02 09:17:36  Shared  RemoteRunId	31236762

後話

其實我想說，【2】中以 Ural1519 Formula 1 作為插頭DP入門並不合適. 並不是說題目難才不合適入門。它不合適的理由在於本題考慮的僅僅是插頭存在與否（用01刻畫即可），Ural1519還在插頭存在與否這個問題的基礎上雜糅了連通性狀態（即增加了一個維度，用三進制刻畫輪廓線狀態，而不是本題用二進制就可以刻畫了）.雜糅連通性的理由在於Ural1519需要用一個哈密頓迴路而不是本題任意多個. 關於Ural1519後面肯定會寫題解的.

因為插頭DP的本質就是狀壓DP輪廓線的插頭狀態. 所以本題雖然較為簡單（事實上可能已經是最簡單的插頭DP問題了,因為只需要考慮輪廓線上的m+1段存在還是不存在插頭），但是完整的說明了插頭DP的整個分析過程, 作為入門插頭DP是最為合適不過的了.

參考

【1】https://yfsyfs.github.io/2019/10/31/poj-1185-%E7%82%AE%E5%85%B5%E9%98%B5%E5%9C%B0-%E7%BB%8F%E5%85%B8%E7%8A%B6%E5%8E%8BDP/

【2】《基於連通性狀態壓縮的動態規劃問題長沙市雅禮中學陳丹琦》