●HDU 3689 Infinite monkey theorem

题链：

http://acm.hdu.edu.cn/showproblem.php?pid=3689
题解：

KMP，概率dp
（字符串都从1位置开始）
首先对模式串S建立next数组。
定义dp[i][j]表示猴子打的串长度为i，且该串的后缀与模式串最多匹配到j位置的概率。
显然dp[0][0]=1，
考虑如何转移：
枚举下一个打出的字符为c，然后用kmp的next数组找到模式串中可以继续匹配的位置k。
即：k=j+1; while(k&&S[k]!=c) k=next[k];
然后将dp[i][j]贡献给dp[i+1][k]，由全概率公式可得到的：
"猴子打了i个字符，最多匹配到模式串的第j个字符"这个事件为前提条件时，
有p(c)的概率发生"猴子打了i+1个字符，最多匹配到了模式串的第k个字符"这个事件。
所以dp[i+1][k]+=dp[i][j]*p(c)

代码：

#include<bits/stdc++.h>

using namespace std;

char key[30];

double p[30],dp[1005][15],ans;

int nxt[15];

int C,N;

void buildnxt(char *S){

	int n=strlen(S+1),j,k;

	nxt[1]=0; j=1; k=0;

	while(j<=n){

		if(k==0||S[j]==S[k]){

			j++; k++; nxt[j]=k;

		}

		else k=nxt[k];

	}

}

int main(){

	static char S[15];

	while(1){

		scanf("%d%d",&C,&N);

		if(!C&&!N) break;

		for(int i=1;i<=C;i++)

			scanf(" %c%lf",&key[i],&p[i]);

		scanf("%s",S+1);

		int len=strlen(S+1);

		buildnxt(S);

		for(int i=0;i<=N;i++)

			for(int j=0;j<=len;j++) dp[i][j]=0;

		dp[0][0]=1;

		for(int i=0;i<N;i++)

			for(int j=0;j<len;j++){

				if(dp[i][j]==0) continue;

				for(int c=1;c<=C;c++){

					int k=j+1;

					while(k&&S[k]!=key[c]) k=nxt[k];

					dp[i+1][k]+=dp[i][j]*p[c];

				}

			}

		ans=0;

		for(int i=1;i<=N;i++) ans+=dp[i][len];

		printf("%.2lf%%\n",ans*100);

	}

	return 0;

}

巴特西

●HDU 3689 Infinite monkey theorem

最新文章

热门文章