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