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;
}