簡單易懂、從零開始的插頭DP (一)正如前麵寫的那樣，是從蒟蒻的視點整理總結的。 更改了一些順序，更改了一些細節。 方便蒟蒻的學習理解)至少本339蒻是這樣。 結實的吐司可以直接看其他大人物的博客，學得更快。

你必須學習的前知識：狀態壓縮DP

雖然還不會學習，但是我推薦學習的前置知識。 zrdxrk/p論文成功之前，建議先讀博客再讀。

《基於連通性狀態壓縮的動態規劃問題》

什麽是塞DP是顯而易見的，是關於塞的動態規劃。 那麽什麽是插頭呢？

如圖所示，在網格中，畫一個關於網格點的閉合電路。

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

對於電路中的任一個網格，可以看到四條邊中隻有兩條與表示路徑的藍線相交。 這也很清楚。 進去一次，出來一次，c (4，2 )=6。

草莓视频黄片在线看現在把格子中的藍線從格子的中心指向外麵。

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

結合例題，這個主題是洛穀模板問題的弱化版，很多博客都放在模板問題之後的第一個問題上。 結合個人經驗，我認為比模板問題更適合第一個問題。

主題： HDU1693 or洛穀P5074

主題：推出n*m網格，部分網格不鋪紗，其他網格必須鋪貼，可形成多個閉合回路。 有幾種鋪法？ (1=n，m=12 ) ) )。

那麽，將電路模型製成插頭模型有什麽好處和性質呢？

1 )首先，如果格子上方的格子有下插頭，可以看到該格子一定有上插頭。 其他方向相似。

按照2:1的方法設置插頭，最後一定會構成電路。

3 )一個方格的合理取值隻與相鄰的方格有關。

觀察之三，它表明實際上沒有效果。 假設對每個網格執行從上至下、從左至右的處理，則可以記錄網格的一部分的狀態，並且不需要更多網格的具體狀態。

如上圖所示，關於當前的網格，隻知道紅色的網格即可，進而上網格的具體取法不再影響以下的未處理的網格。

掌握了狀態壓縮的你一定能很容易地算出狀態總數。 每個方格有6種，維護n個方格。 總共隻有6 n 6^n 6n的狀態，是的，結束了，2e9的狀態。

別急，草莓视频黄片在线看真的需要2e9的狀態嗎？ 在這些格子中，指向彼此處理過的格子的插頭，顯然是廢棄物信息。 草莓视频黄片在线看實際上隻是知道這些插頭。

藍色是其他格子需要的，黃色是現在格子需要的。草莓视频黄片在线看叫紅色的這個線為輪廓線隻需知道該輪廓線上是否存在m 1個箭頭即可。 共計2米22^ m *22 m2個狀態。 再乘坐n和m的話，時空的複雜性會變得充裕。

那麽，怎麽實現？ 草莓视频黄片在线看必須解決兩個問題。

1 )如果知道這些插頭，這個方格該怎麽填？

2 )填寫此方格後，請告訴我下一個方格所需的插頭狀態，如何從更特殊的、上一行結尾改為下一行開頭。

這兩個問題其實都不是很難。 稍微想想，就可以獨立求解了。 我建議你三思而後行。 圖製止以下大法。

問題1 :

0 :這個格子走不動的話，左側和上方的插頭不能存在。

1 )當前格柵有左側插頭和上方插頭時，隻有一種合理的填補方式。

2 )如果隻存在左側插頭，有兩種合理的填補方式。

3 )如果隻存在上麵的插頭，它和前麵的類型相似，也是兩種填補方法。

4 )如果不存在呢？ 隻有一種填補方法

問題2 :

解開問題1後，顯然也得到了問題2的解答。 畢竟，草莓视频黄片在线看填滿了這個格子，自然知道插頭的分布。 唯一特殊的是從上一行結束到此行結束的處理。 前麵一行的結尾不是有右插頭。 那麽，如果在表示上一行結束狀態的最後，去掉表示右插頭是否存在的位置，添加表示沒有左插頭的位，不就表示該行的第一個狀態嗎？ 為了便於編寫，下麵的代碼在dp[i][0][mask]中表示遷移後前一行的結束狀態。

到此為止，草莓视频黄片在线看得到了理解方法。 成熟的評價機應該自動交流吧。 插頭DP還是需要多寫。 千萬要自己寫。 請不要忘記。 這隻是模板問題的弱化。

這裏提供代碼(洛穀交流)

# include iosestream # include stdio.h # includecstringusingnamespacestd； int n，m，maxk，a[13][13]； 龍龍DP [ 13 ] [ 13 ] [ 114 ]； () ) ) ) ) )。

;maxk=(1<<(m+1))-1;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}memset(dp,0,sizeof(dp));}void solve(){int prei,prej;dp[0][m][0]=1;for (int i=1;i<=n;i++){for (int k=0;k<=maxk;k++){dp[i][0][k<<1]=dp[i-1][m][k];}for (int j=1;j<=m;j++){prei=i;prej=j-1;for (int k=0;k<=maxk;k++){int b1=(k>>(j-1))&1;int b2=(k>>j)&1;if (!a[i][j]){if (!b1&&!b2) dp[i][j][k]+=dp[prei][prej][k];}else if (!b1&&!b2){dp[i][j][k+(1<<j)+(1<<(j-1))]+=dp[prei][prej][k];}else if (b1&&!b2){dp[i][j][k]+=dp[prei][prej][k];dp[i][j][k+(1<<(j-1))]+=dp[prei][prej][k];}else if (!b1&&b2){dp[i][j][k]+=dp[prei][prej][k];dp[i][j][k-(1<<(j-1))]+=dp[prei][prej][k];}else if (b1&&b2){dp[i][j][k-(1<<j)-(1<<(j-1))]+=dp[prei][prej][k];}}}}printf("%lld\n",dp[n][m][0]);}int main(){int t;scanf("%d",&t);while (t--){init();solve();}return 0;}

到這裏，插頭DP算是入門了一半了，下一篇博客，將會介紹模板題和一係列的簡單應用。這道題目裏的狀態是二進製狀態壓縮，下麵的題目則不然，敬請期待。想必，多半，大概，也許，可能，能日更吧。

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