Posted on 2010-10-29 23:17
Uriel 阅读(385)
评论(2) 编辑 收藏 引用 所属分类:
DP 、
字符串处理 、
比赛题解
题意：有n个键，按每个键有一概率Pi，给定一个字符串S，问按m次敲出这个字符串的概率
现场赛茫茫多的队伍过了这题，可以我们学校两队都没过。。= =
在HDOJ上组队做杭州赛的题的时候纠结了半天也没过。。赛后听说思路就是KMP，DP，我状态转移处理有问题。。
今天又搞了一晚上，请教Ziroy大牛之后发现错误原因在s状态不用处理
思路：dp转移方程很好想，dp[i][j]表示已经按了i次，当前状态是j(S的第j个字母)，概率是多少
具体实现过程见代码及注释
//Problem: HDOJ 3689
//Source: 2010 Hangzhou Regional On-Site J Infinite monkey theorem
//Solution: KMP+DP(like DFA)
//Status: Accepted
//Running Time: 15Ms
//Author: Uriel
//2010.10.29
#include<stdio.h>
#include<string.h>
double dp[1050][20],dd[20];
char st[30],ch[30];
double p[30];
int nxt[30],s;
void GetNext(char* str)
{
nxt[0]=-1;
int i=0,j=-1;
while(str[i]){
if(j==-1 || str[i]==str[j]){
i++; j++; nxt[i]=j;
}
else j=nxt[j];
}
}
int main(){
int n,m;
int i,j,k;
while(scanf("%d %d",&n,&m),n|m){
for(i=0;i<n;i++){
scanf("%s",st);
ch[i]=st[0];
scanf("%lf",&p[i]);
}
scanf("%s",st);
for(i=0;i<=m;++i){
for(j=0;j<=s;++j)dp[i][j]=0.0;
}
s=strlen(st);
GetNext(st);
dp[0][0]=1.0;
for(i=1;i<=m;i++){ //共按m次
for(j=0;j<s;j++){ //枚举当前状态,不用考虑j=s,因为这时已经满足要求,不用算下去!!
for(k=0;k<n;++k){ //枚举当前这次按哪个键
if(!j){ //如果当前状态是还没有按出正确串的前缀
if(ch[k]==st[0])dp[i][1]+=dp[i-1][0]*p[k]; //如果这次按的是川的第一个字母,状态从0变为1
else //否则0状态的概率累加
dp[i][0]+=dp[i-1][0]*p[k];
}
else if(ch[k]==st[j]){ //如果当前按对了该串当前状态的后一个字母
dp[i][j+1]+=dp[i-1][j]*p[k]; //状态+1
}
else{
int tp=j;
while(tp>-1 && ch[k]!=st[tp])tp=nxt[tp]; //利用KMP的Next函数当前状态计算按下k之后的状态(能匹配的前缀长度)
if(tp==-1)dp[i][0]+=dp[i-1][j]*p[k]; //如果当前匹配失败,状态变为0，且累加状态0的概率
else //否则状态为tp+1,状态tp+1的概率累加
dp[i][tp+1]+=dp[i-1][j]*p[k];
}
}
}
}
double ans=0.0;
for(i=1;i<=m;++i)ans+=dp[i][s];//所有长度能得到状态s的概率之和即为所求
printf("%.2f%%\n",100*ans);
}
return 0;
} 这么大水的题搞了这么久。。而且字符串又是我的任务。。杯具。。
下周三去成都，39h45min，第一次坐这么长时间火车。。
祈祷DSW Chengdu Regional 好运。。Regional是如此的宝贵。。不知道以后还有没有机会。。