本文从WordPress迁移而来, 查看全部WordPress迁移文章
字符串dp
题意:给出n个字符集,并给出敲打每个字符的概率(保证和为1),给出m,表示会敲打m次键盘。给出一个目标单词,问敲完键盘后能敲出这个单词的期望是多少
设单词长度为wl,从1到wl标号
设敲打次数为tot,从1到tot标号
dp[i][j] : 表示敲完第i次键盘后,形成的长度为i的字符串的后缀中,匹配了单词中的前j个字符,且没出现过该单词的概率
dp[tot][0] + dp[tot][1] + dp[tot][2] + dp[tot][2]…………..dp[tot][wl-1]
这些其实就表示了不能敲出单词的期望,要求能敲出,用1-sum即可
现在来看怎么转移
首先需要构建一个数组
mat[i][j],表示,匹配了前i个字母后,敲入第j个字符(字符集中第j个字符),能产生的最大匹配
如: 目标单词 abaabab
i = 3,匹配了3个,即aba,然后敲入下一个字符
敲a:aba + a = abaa —> 结果为4(abaa)
敲b:aba + b = abab —> 结果为2(ab)
mat[i][j]的构建比较随意,因为单词很短只有10,可以暴力,高级的做法就是KMP或者AC自动机了
状态转移方程: dp[i+1][mat[j][k]] += dp[i][j] * p[k]; //k表示字符集的第k个字符,p[k]是敲这个字符的概率
1 |
|