hdu 3689 Infinite monkey theorem

本文从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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define N 1010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,wl;
char cha[30];
double p[30];
int mat[N][30];
string word;
string pre[30];
double dp[N][20];

void Match(){
cl(mat,0);
for(int i = 0; i <= wl; i++)
pre[i] = word.substr(0,i);
//for(int i = 0; i <= wl; i++)
// cout << pre[i] << endl;
for(int i = 0; i < wl; i++)
for(int j = 0; j < n; j++){
string now = pre[i] + cha[j];
for(int k = 0; k < now.length(); k++){
string suf = now.substr(k);
for(int t = wl; t >= 0; t--)
if(suf == pre[t]){
mat[i][j] = max(mat[i][j],t); break;
}
}
}
/*
for(int i = 0; i <= wl; i++)
for(int j = 0; j < n ;j++)
printf("mat[%d][%d] = %d\n",i,j,mat[i][j]);
*/
}

void DP(){
cl(dp,0);
//for(int i = 0; i < wl; i++)
// dp[0][i] = 1.00;
dp[0][0] = 1.00;
for(int i = 0; i < tot; i++)
for(int j = 0; j < wl; j++)
for(int k = 0; k < n; k++){
dp[i+1][mat[j][k]] += dp[i][j] * p[cha[k] - 'a'];
}
double ans = 0;
for(int i = 0; i < wl; i++)
ans += dp[tot][i];
printf("%.2lf",100.00-ans*100.00);
puts("%");
}

int main(){
//freopen("grated.txt","w",stdout);
while(scanf("%d%d",&n,&tot)!=EOF){
if(!n && !tot) break;
for(int i = 0; i < n; i++){
char s[5]; double x;
scanf("%s%lf",s,&x);
cha[i] = s[0]; p[s[0] - 'a'] = x;
}
cin >> word;
wl = word.length();
Match();
DP();
}
return 0;
}