簡(jiǎn)單易懂、從零開(kāi)始的插頭DP (一)正如前面寫(xiě)的那樣，是從蒟蒻的視點(diǎn)整理總結的。 更改了一些順序，更改了一些細節。 方便蒟蒻的學(xué)習理解)至少本339蒻是這樣。 結實(shí)的吐司可以直接看其他大人物的博客，學(xué)得更快。
你必須學(xué)習的前知識：狀態(tài)壓縮DP
雖然還不會(huì )學(xué)習，但是我推薦學(xué)習的前置知識。 zrdxrk/p論文成功之前，建議先讀博客再讀。
《基于連通性狀態(tài)壓縮的動(dòng)態(tài)規劃問(wèn)題》
什么是塞DP是顯而易見(jiàn)的，是關(guān)于塞的動(dòng)態(tài)規劃。 那么什么是插頭呢？
如圖所示，在網(wǎng)格中，畫(huà)一個(gè)關(guān)于網(wǎng)格點(diǎn)的閉合電路。
對于每個(gè)方格、內部，有六種情況
對于電路中的任一個(gè)網(wǎng)格，可以看到四條邊中只有兩條與表示路徑的藍線(xiàn)相交。 這也很清楚。 進(jìn)去一次，出來(lái)一次，c (4，2 )=6。
我們現在把格子中的藍線(xiàn)從格子的中心指向外面。
這個(gè)箭頭，也就是所謂的插頭。
結合例題，這個(gè)主題是洛谷模板問(wèn)題的弱化版，很多博客都放在模板問(wèn)題之后的第一個(gè)問(wèn)題上。 結合個(gè)人經(jīng)驗，我認為比模板問(wèn)題更適合第一個(gè)問(wèn)題。
主題： HDU1693 or洛谷P5074
主題：推出n*m網(wǎng)格，部分網(wǎng)格不鋪紗，其他網(wǎng)格必須鋪貼，可形成多個(gè)閉合回路。 有幾種鋪法？ (1=n，m=12 ) ) )。
那么，將電路模型制成插頭模型有什么好處和性質(zhì)呢？
1 )首先，如果格子上方的格子有下插頭，可以看到該格子一定有上插頭。 其他方向相似。
按照2:1的方法設置插頭，最后一定會(huì )構成電路。
3 )一個(gè)方格的合理取值只與相鄰的方格有關(guān)。
觀(guān)察之三，它表明實(shí)際上沒(méi)有效果。 假設對每個(gè)網(wǎng)格執行從上至下、從左至右的處理，則可以記錄網(wǎng)格的一部分的狀態(tài)，并且不需要更多網(wǎng)格的具體狀態(tài)。
如上圖所示，關(guān)于當前的網(wǎng)格，只知道紅色的網(wǎng)格即可，進(jìn)而上網(wǎng)格的具體取法不再影響以下的未處理的網(wǎng)格。
掌握了狀態(tài)壓縮的你一定能很容易地算出狀態(tài)總數。 每個(gè)方格有6種，維護n個(gè)方格。 總共只有6 n 6^n 6n的狀態(tài)，是的，結束了，2e9的狀態(tài)。
別急，我們真的需要2e9的狀態(tài)嗎？ 在這些格子中，指向彼此處理過(guò)的格子的插頭，顯然是廢棄物信息。 我們實(shí)際上只是知道這些插頭。
藍色是其他格子需要的，黃色是現在格子需要的。我們叫紅色的這個(gè)線(xiàn)為輪廓線(xiàn)只需知道該輪廓線(xiàn)上是否存在m 1個(gè)箭頭即可。 共計2米22^ m *22 m2個(gè)狀態(tài)。 再乘坐n和m的話(huà)，時(shí)空的復雜性會(huì )變得充裕。
那么，怎么實(shí)現？ 我們必須解決兩個(gè)問(wèn)題。
1 )如果知道這些插頭，這個(gè)方格該怎么填？
2 )填寫(xiě)此方格后，請告訴我下一個(gè)方格所需的插頭狀態(tài)，如何從更特殊的、上一行結尾改為下一行開(kāi)頭。
這兩個(gè)問(wèn)題其實(shí)都不是很難。 稍微想想，就可以獨立求解了。 我建議你三思而后行。 圖制止以下大法。
問(wèn)題1 :
0 :這個(gè)格子走不動(dòng)的話(huà)，左側和上方的插頭不能存在。
1 )當前格柵有左側插頭和上方插頭時(shí)，只有一種合理的填補方式。
2 )如果只存在左側插頭，有兩種合理的填補方式。
3 )如果只存在上面的插頭，它和前面的類(lèi)型相似，也是兩種填補方法。
4 )如果不存在呢？ 只有一種填補方法
問(wèn)題2 :
解開(kāi)問(wèn)題1后，顯然也得到了問(wèn)題2的解答。 畢竟，我們填滿(mǎn)了這個(gè)格子，自然知道插頭的分布。 唯一特殊的是從上一行結束到此行結束的處理。 前面一行的結尾不是有右插頭。 那么，如果在表示上一行結束狀態(tài)的最后，去掉表示右插頭是否存在的位置，添加表示沒(méi)有左插頭的位，不就表示該行的第一個(gè)狀態(tài)嗎？ 為了便于編寫(xiě)，下面的代碼在dp[i][0][mask]中表示遷移后前一行的結束狀態(tài)。
到此為止，我們得到了理解方法。 成熟的評價(jià)機應該自動(dòng)交流吧。 插頭DP還是需要多寫(xiě)。 千萬(wàn)要自己寫(xiě)。 請不要忘記。 這只是模板問(wèn)題的弱化。
這里提供代碼(洛谷交流)
# include iostream # 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算是入門(mén)了一半了，下一篇博客，將會(huì )介紹模板題和一系列的簡(jiǎn)單應用。這道題目里的狀態(tài)是二進(jìn)制狀態(tài)壓縮，下面的題目則不然，敬請期待。想必，多半，大概，也許，可能，能日更吧。
電腦前這個(gè)努力的帥氣身影是誰(shuí)呢？そう 私 です