Posted on 2010-10-29 23:17
Uriel 閱讀(411)
評論(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是如此的寶貴。。不知道以后還有沒有機會。。