題意：

? ? ?給出n個(gè)串，求任意長(zhǎng)度為m的字符串包含串的個(gè)數(shù)的期望。(n<=8,m<=14,給定串的長(zhǎng)度不超過12)。

?

?

Solution：

? ? ?首先可以想到應(yīng)該用概率DP,我們需要至少3維,dp[i][j][k]表示第i個(gè)數(shù)字為j,已經(jīng)包含了k個(gè)串的概率.

? ? ?然后,問題是找到狀態(tài)轉(zhuǎn)移的方法

? ? ?由于是字符串相關(guān),AC自動(dòng)機(jī)應(yīng)該是第一個(gè)想到的.

? ? ?然后注意到,對(duì)于k個(gè)串的k,直接求并不好維護(hù),也沒辦法判斷重復(fù)的 .由于只有8個(gè)串,自然就想到用更簡(jiǎn)單的方法,用狀態(tài)壓縮來存已經(jīng)包含了哪些串.

? ? ?在建trie圖的時(shí)候，要注意一個(gè)結(jié)點(diǎn)的狀態(tài)應(yīng)該是包含了它的fail節(jié)點(diǎn)的狀態(tài)的.

? ? ?從u到v的轉(zhuǎn)移

? ? ? ? ? ? ? ? ?dp[i+1][u][sta[u]|sta[v]]+=dp[i][v][sta[v]]

?

#include <iostream> #include <queue> #include <cstdio> #include <string> #include <cstring> using namespace std; const int SD = 26; const int MAXL = 1000; struct Tire {int next[MAXL][SD], fail[MAXL], eofs[MAXL];int Root, cnt;int newnode() {for (int i = 0; i < SD; i++) next[cnt][i] = -1;eofs[cnt++] = 0;return cnt - 1;}void init() {cnt = 0;Root = newnode();}void Ins (char buf[], int k) {int len = strlen (buf);int now = Root;for (int i = 0; i < len; i++) {if (next[now][buf[i] - 'a'] == -1)next[now][buf[i] - 'a'] = newnode();now = next[now][buf[i] - 'a'];}eofs[now] |= (1 << k);}void build() {queue<int> ql;fail[Root] = Root;for (int i = 0; i < SD; i++) {if (next[Root][i] == -1)next[Root][i] = Root;else {fail[next[Root][i]] = Root;ql.push (next[Root][i]);}}while (!ql.empty() ) {int now = ql.front(); ql.pop();eofs[now] |= eofs[fail[now]];for (int i = 0; i < SD; i++)if (next[now][i] == -1) {next[now][i] = next[fail[now]][i];}else {fail[next[now][i]] = next[fail[now]][i];ql.push (next[now][i]);}}} } AC; int Cs, n, m; char s[20]; double dp[20][400][1 << 9], tmp = 1. / 26; int main() {scanf ("%d", &Cs);while (Cs--) {memset (dp, 0, sizeof dp);AC.init();scanf ("%d %d", &n, &m);for (int i = 0; i < n; i++) {scanf ("%s", s);AC.Ins (s, i);}AC.build();dp[0][0][0] = 1;for (int i = 0; i < m; i++)for (int u = 0; u < AC.cnt; u++)for (int st = 0; st < (1 << n); st++)if (dp[i][u][st] > 0)for (int j = 0; j < SD; j++) {int v = AC.next[u][j];dp[i + 1][v][st | AC.eofs[v]] += dp[i][u][st] * tmp;}double ans = 0;for (int i = 0; i < AC.cnt; i++)for (int st = 0; st < (1 << n); st++)if (dp[m][i][st] > 0) {int sum = 0;for (int k = 0; k < n; k++)if (st & (1 << k) ) sum++;ans += dp[m][i][st] * sum;}printf ("%.6f\n", ans);} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/keam37/p/4442799.html

總結(jié)

以上是生活随笔為你收集整理的WHU 1572 Cyy and Fzz (AC自动机 dp )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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