首页 > 代码库 > [HDU 3689]Infinite monkey theorem (KMP+概率DP)
[HDU 3689]Infinite monkey theorem (KMP+概率DP)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3689
黄老师说得对，题目只有做wa了才会有收获，才会有提高。
题意：一个猴子敲键盘，键盘上有n个键，猴子敲第i个键的概率是p[i]，问敲m次后形成的字符串里出现给定串的概率是多少。
这实际上就跟那个ac自动机转为trie图然后dp一样的。
类似的题目有POJ 2778，这篇题解不错：http://blog.csdn.net/luyuncheng/article/details/8643001
只不过是一个串，而不是一堆串，因此就可以把AC自动机换为KMP来搞。
设dp[i][j]表示猴子敲了i次键盘走到状态为j的点上
注意next数组的含义，我开始就是没有理解透彻next数组的意思。
如果说str[i]!=c那么str[next[i]]也一定不是c
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int next[20],n,m;12 char str[20];13 double f[30],dp[1100][20];14 15 void get_next(int m,const char* str){16 int j = 0;17 next[1] = 0;18 for( int i=2;i<m;i++ ){19 while( j>0 && str[j+1]!=str[i] ) j = next[j];20 if( str[j+1] == str[i] ) j++;21 next[i] = j;22 }23 }24 25 int main(){26 while(scanf("%d%d",&n,&m)!=EOF){27 if( n==0&&m==0 ) break;28 char c[2]; double d;29 memset(f,0,sizeof(f));30 vector<int> v;31 for(int i=0;i<n;i++){32 scanf("%s%lf",c,&d);33 f[c[0]-‘a‘] = d;34 v.push_back(c[0]-‘a‘);35 }36 scanf("%s",str+1);37 int len = strlen(str+1);38 memset(next,0,sizeof(next));39 get_next(len,str);40 memset(dp,0,sizeof(dp));41 dp[0][0] = 100;42 for(int i=0;i<m;i++){43 for(int j=0;j<len;j++){44 for(int k=0;k<v.size();k++){45 int fa = j;46 while( fa&&v[k]!=str[fa+1]-‘a‘ ) fa = next[fa];47 if( str[fa+1]-‘a‘==v[k] ) fa++;48 dp[i+1][fa] += dp[i][j] * f[v[k]];49 }50 }51 }52 double sum = 0;53 for(int i=0;i<=m;i++) sum += dp[i][len];54 printf("%.2f%%\n",sum);55 }56 return 0;57 }
或者说可以用矩阵来实现
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int next[20],n,m;12 char str[20];13 double f[30];14 15 void get_next(int m,const char* str){16 int j = 0;17 next[1] = 0;18 for( int i=2;i<=m;i++ ){19 while( j>0 && str[j+1]!=str[i] ) j = next[j];20 if( str[j+1] == str[i] ) j++;21 next[i] = j;22 }23 }24 25 struct Matrix{26 double m[20][20];27 Matrix(){28 memset(m,0,sizeof(m));29 }30 Matrix operator*(const Matrix &a){31 Matrix res;32 for(int i=0;i<20;i++){33 for(int j=0;j<20;j++){34 for(int k=0;k<20;k++){35 res.m[i][j] += m[i][k] * a.m[k][j];36 }37 }38 }39 return res;40 }41 };42 43 Matrix pow_bin(Matrix x,int e){44 Matrix res;45 for(int i=0;i<20;i++) res.m[i][i] = 1;46 while( e ){47 if( e&1 ) res = res * x;48 x = x*x;49 e>>=1;50 }51 return res;52 }53 54 int main(){55 while(scanf("%d%d",&n,&m)!=EOF){56 if( n==0&&m==0 ) break;57 char c[2]; double d;58 vector<int> v;59 memset(f,0,sizeof(f));60 for(int i=0;i<n;i++){61 scanf("%s%lf",c,&d);62 f[c[0]-‘a‘] = d;63 v.push_back(c[0]-‘a‘);64 }65 getchar();66 gets(str+1);67 int len = strlen(str+1);68 get_next(len,str);69 Matrix ma;70 for(int i=0;i<len;i++){71 for(int j=0;j<v.size();j++){72 int fa = i;73 while( fa&&str[fa+1]-‘a‘!=v[j] ) fa = next[fa];74 if( str[fa+1]-‘a‘==v[j] ) fa++;75 ma.m[i][fa] += f[v[j]];76 }77 }78 Matrix res = pow_bin(ma,m);79 double ans = 0;80 for(int i=0;i<len;i++){81 ans += res.m[0][i];82 }83 printf("%.2f%%\n",100-ans*100);84 }85 return 0;86 }
[HDU 3689]Infinite monkey theorem (KMP+概率DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。