轉(zhuǎn)載標記處：http://blog.csdn.net/woshi250hua/article/details/7599472

題目大意：給定m個DNA病毒序列，求堿基構(gòu)成的長度為n且含有兩個以上DNA病毒序列,結(jié)果對10007取模。

解題思路：本題代碼量大，較為綜合，需用到AC自動機改造而成的Trie圖、DP思想、矩陣快速冪。

? ? ?如果n比較小，那么本題可以用DP解，由于題目明顯的有三個狀態(tài)，未含病毒串、含一個病毒串，含兩個及兩個以上病毒，根據(jù)這三個就可以寫出一個狀態(tài)轉(zhuǎn)移方程。但是本題可以簡化一下，先求出總的組合種數(shù)，再減去含有一個病毒串和未含病毒串的種數(shù)就是解了。那么狀態(tài)就只有2個。

? ? ?狀態(tài)轉(zhuǎn)移方程為：if (j->next 為病毒串） ? ? ? ?dp[i+1][j->next][1] += dp[i][j][0] ;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else if (j->next非病毒串) ? dp[i+1][j->next][1] ?+= dp[i][j][1];

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?dp[i+1][j->next][0] += dp[i][j][0];

? ??但是本題n特別大，必須用矩陣進行優(yōu)化。先將Trie圖轉(zhuǎn)化為一個(total * 2) * （total * 2)(total為總節(jié)點數(shù)）可達矩陣，如果i ?< total，那說明這個節(jié)點和他的后綴不含有病毒串，如果i > total，那說明這個節(jié)點和他的后綴含有1個病毒串。

? ? 具體實現(xiàn)是這樣的，if (i->next->flag) matrix[i][i->next+total]++;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else matrix[i][i->next]++,matrix[i+total][i->next+total]++;

? ? ?這樣，矩陣就被分成四塊相當于四個象限，第2個象限（i和j都小于total）怎么走都不會出現(xiàn)病毒串，那么經(jīng)過A^n，他們的值就是最后病毒序列為0個的種數(shù)。第1個象限表示i走到j-total會出現(xiàn)一個病毒DNA序列，第四個象限i-total走到j-total，原來含1個病毒串現(xiàn)在還是1個。

這里的矩陣優(yōu)化dp確實做得很巧妙，實際上矩陣優(yōu)化dp只能夠處理一維和二維的狀態(tài)，在二維的情況下，dp[i][]只能夠與dp[i-1][]有關。如果大于二維，比如本題的情況，就想辦法分解成二維的，以本題為例，第三維的狀態(tài)只有0和1兩種可能，我們實際上是把第二維擴大了1倍，得到的是一個（2*tot）*（2*tot）的狀態(tài)矩陣，這樣就可以表示出第三維的狀態(tài)了。剩下的就是按照原來的狀態(tài)轉(zhuǎn)移方程來填矩陣的系數(shù)了。

這道題讓我想起了上一道DNA Sequence，也是AC自動機+矩陣，現(xiàn)在再來看這道題，其實也就是先列出狀態(tài)轉(zhuǎn)移方程，再構(gòu)造的優(yōu)化矩陣。

總結(jié)

以上是生活随笔為你收集整理的hdu 3962(AC自动机+矩阵优化dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。