首页 > 代码库 > HDU 3689 Infinite monkey theorem [KMP DP]
HDU 3689 Infinite monkey theorem [KMP DP]
Infinite monkey theorem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1702 Accepted Submission(s): 882
Problem Description
Could you imaging a monkey writing computer programs? Surely monkeys are smart among animals. But their limited intelligence is no match for our human beings. However, there is a theorem about monkeys, and it states that monkeys can write everything if given enough time.
The theorem is called “Infinite monkey theorem”. It states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, which of course includes the programs you are about to write (All computer programs can be represented as text, right?).
It’s very easy to prove this theorem. A little calculation will show you that if the monkey types for an infinite length of time the probability that the output contains a given text will approach 100%.
However, the time used is too long to be physically reasonable. The monkey will not be able to produce any useful programs even if it types until the death of the universe. To verify this and ensure that our human beings are not replaceable by monkeys, you are to calculate the probability that a monkey will get things right.
The theorem is called “Infinite monkey theorem”. It states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, which of course includes the programs you are about to write (All computer programs can be represented as text, right?).
It’s very easy to prove this theorem. A little calculation will show you that if the monkey types for an infinite length of time the probability that the output contains a given text will approach 100%.
However, the time used is too long to be physically reasonable. The monkey will not be able to produce any useful programs even if it types until the death of the universe. To verify this and ensure that our human beings are not replaceable by monkeys, you are to calculate the probability that a monkey will get things right.
Input
There will be several test cases.
Each test case begins with a line containing two integers n and m separated by a whitespace (2<=n<=26, 1<=m<=1000). n is the number of keys on the typewriter and the monkey will hit these keys m times. Thus the typewriter will finally produce an output of m characters.
The following n lines describe keys on the typewriter. Each line has a lower case letter and a real number separated by a whitespace. The letter indicates what the typewriter will produce if the monkey hits that key and the real number indicates the probability that the monkey will hit this key. Two hits of the monkey are independent of each other (Two different hits have the same probability for a same key), and sum of all the probabilities for each key is ensured to be 1.
The last line of the test case contains a word composed of lower case letters. The length of the word will be less than or equal to 10.
The input will end with a line of two zeros separated by a whitespace. This line should not be processed.
Each test case begins with a line containing two integers n and m separated by a whitespace (2<=n<=26, 1<=m<=1000). n is the number of keys on the typewriter and the monkey will hit these keys m times. Thus the typewriter will finally produce an output of m characters.
The following n lines describe keys on the typewriter. Each line has a lower case letter and a real number separated by a whitespace. The letter indicates what the typewriter will produce if the monkey hits that key and the real number indicates the probability that the monkey will hit this key. Two hits of the monkey are independent of each other (Two different hits have the same probability for a same key), and sum of all the probabilities for each key is ensured to be 1.
The last line of the test case contains a word composed of lower case letters. The length of the word will be less than or equal to 10.
The input will end with a line of two zeros separated by a whitespace. This line should not be processed.
Output
For each test case, output one line containing the probability that the given word will appear in the typewriter’s output. The output should be in percentage format and numbers should be rounded to two digits after the decimal point.
Source
2010 Asia Hangzhou Regional Contest
题意:
字符集中有一些字符(最多26个),给出每个字符的出现概率(它们的和保证为1)
再给出一个子串B
求:任给一个长度为N的字符串A(只能包含字符集中的字符),使得B是A的子串的概率。
一边生成A,一边用KMP匹配B
f[i][j]表示生成到i位,当前匹配到B的j位的概率
枚举下一个字符,然后用KMP匹配就行了....匹配到now,就是f[i+1][now]+=f[i][j]*p[k]
#include <iostream>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1005,M=15;int cn,n,m,fail[N];char c[2],b[N],key[N];double p[N],f[N][M];void getFail(int n,char s[]){ fail[1]=0; for(int i=2;i<=n;i++){ int j=fail[i-1]; while(j&&s[j+1]!=s[i]) j=fail[j]; fail[i]=s[j+1]==s[i]?j+1:0; }}void dp(){ memset(f,0,sizeof(f)); f[0][0]=1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(f[i][j]) for(int k=1;k<=cn;k++){ int now=j; while(now&&b[now+1]!=key[k]) now=fail[now]; now+=b[now+1]==key[k]; f[i+1][now]+=f[i][j]*p[k]; } double ans=0; for(int i=1;i<=n;i++) ans+=f[i][m]; ans*=100; printf("%.2lf%%\n",ans);}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d%d",&cn,&n)!=EOF&&(cn||n)){ for(int i=1;i<=cn;i++){ scanf("%s%lf",c,&p[i]); key[i]=c[0]; } scanf("%s",b+1); m=strlen(b+1); getFail(m,b); dp(); }}
HDU 3689 Infinite monkey theorem [KMP DP]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。