dp套dp（动态规划）
dp套dp
這是一個(gè)對(duì)于一類動(dòng)態(tài)規(guī)劃的計(jì)數(shù)問題的處理方法，問題常常是如果形式確定就可以直接dp，但是現(xiàn)在卻要求滿足某個(gè)要求的所有方案數(shù)，一般的處理方法就是一維負(fù)責(zé)增量構(gòu)造，其他維度用來表示內(nèi)部dp狀態(tài)，然后轉(zhuǎn)移時(shí)候先讓內(nèi)部狀態(tài)轉(zhuǎn)移，然后外部dp對(duì)應(yīng)存儲(chǔ)方案數(shù)。
類似于將內(nèi)部的dp轉(zhuǎn)移變成一個(gè)自動(dòng)機(jī)，可以接受所有不同的轉(zhuǎn)移，然后我們的外層dp就是在自動(dòng)機(jī)上進(jìn)行計(jì)數(shù)。
P4590 [TJOI2018]游園會(huì)
給定一個(gè)長(zhǎng)度為k的字符串，求解長(zhǎng)度為n的字符串中LCS為i的個(gè)數(shù)，對(duì)所有的i輸出答案。
首先對(duì)于LCS的一般處理就是dp，但是這里我們需要處理不同的串，而不是單一的串的問題，所以我們使用dp套dp，然后對(duì)于內(nèi)層狀態(tài)我們需要保存不同串下的對(duì)應(yīng)dp狀態(tài)，那么可以發(fā)現(xiàn)利用差分可以得到一個(gè)長(zhǎng)度為k的01串，那么我們可以將其視作是自動(dòng)機(jī)的狀態(tài)，然后每次新增加一個(gè)字符就可以轉(zhuǎn)移，然后我們只需要在外層再套上一個(gè)dp來計(jì)數(shù)即可。
CF979E Kuro and Topological Parity
https://www.cnblogs.com/wmrv587/p/9051201.html
題意：
給定n個(gè)點(diǎn)，每個(gè)點(diǎn)有黑白兩種顏色（如果沒有顏色，那么你可以把它任意涂成黑色或白色），同時(shí)你可以在這個(gè)圖上任意加入一些邊（當(dāng)然不能加入重邊或自環(huán)），要求：加入的邊必須從編號(hào)小的點(diǎn)指向編號(hào)大的點(diǎn)
我們稱一條好的路徑為經(jīng)過的點(diǎn)為黑白相間的路徑，如果一個(gè)圖好的路徑的總數(shù)%2=p，那么我們稱這個(gè)圖為好的圖，現(xiàn)在給定你n個(gè)點(diǎn)的情況，求這n個(gè)點(diǎn)能組成的好的圖的個(gè)數(shù)，答案取模10^9+7
首先如果圖是一定的，那么我們可以輕易的進(jìn)行dp得到答案，但是現(xiàn)在問題是圖不是一定的，所以我們就需要dp套dp解決，因?yàn)槲覀冎魂P(guān)注路徑個(gè)數(shù)的奇偶性，所以狀態(tài)只需要保留終止點(diǎn)為黑色和白色的點(diǎn)數(shù)的奇偶性，因?yàn)槠渌c(diǎn)都是可連可不連的，然后只需要一個(gè)顏色不同有奇數(shù)個(gè)鏈的點(diǎn)存在，那么最后結(jié)果是奇數(shù)和偶數(shù)的方案都是2i?22^{i-2}2i?2,所以這樣我們就可以做到O(n)的復(fù)雜度了。
總結(jié)
以上是生活随笔為你收集整理的dp套dp（动态规划）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
