Posted on 2010-10-29 23:17
Uriel 閱讀(412)
評論(2) 編輯 收藏 引用 所屬分類:
DP 、
字符串處理 、
比賽題解
題意：有n個鍵，按每個鍵有一概率Pi，給定一個字符串S，問按m次敲出這個字符串的概率
現(xiàn)場賽茫茫多的隊伍過了這題，可以我們學(xué)校兩隊都沒過。。= =
在HDOJ上組隊做杭州賽的題的時候糾結(jié)了半天也沒過。。賽后聽說思路就是KMP，DP，我狀態(tài)轉(zhuǎn)移處理有問題。。
今天又搞了一晚上，請教Ziroy大牛之后發(fā)現(xiàn)錯誤原因在s狀態(tài)不用處理
思路：dp轉(zhuǎn)移方程很好想，dp[i][j]表示已經(jīng)按了i次，當(dāng)前狀態(tài)是j(S的第j個字母)，概率是多少
具體實現(xiàn)過程見代碼及注釋
//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++){ //枚舉當(dāng)前狀態(tài),不用考慮j=s,因為這時已經(jīng)滿足要求,不用算下去!!
for(k=0;k<n;++k){ //枚舉當(dāng)前這次按哪個鍵
if(!j){ //如果當(dāng)前狀態(tài)是還沒有按出正確串的前綴
if(ch[k]==st[0])dp[i][1]+=dp[i-1][0]*p[k]; //如果這次按的是川的第一個字母,狀態(tài)從0變?yōu)?
else //否則0狀態(tài)的概率累加
dp[i][0]+=dp[i-1][0]*p[k];
}
else if(ch[k]==st[j]){ //如果當(dāng)前按對了該串當(dāng)前狀態(tài)的后一個字母
dp[i][j+1]+=dp[i-1][j]*p[k]; //狀態(tài)+1
}
else{
int tp=j;
while(tp>-1 && ch[k]!=st[tp])tp=nxt[tp]; //利用KMP的Next函數(shù)當(dāng)前狀態(tài)計算按下k之后的狀態(tài)(能匹配的前綴長度)
if(tp==-1)dp[i][0]+=dp[i-1][j]*p[k]; //如果當(dāng)前匹配失敗,狀態(tài)變?yōu)?，且累加狀態(tài)0的概率
else //否則狀態(tài)為tp+1,狀態(tài)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];//所有長度能得到狀態(tài)s的概率之和即為所求
printf("%.2f%%\n",100*ans);
}
return 0;
} 這么大水的題搞了這么久。。而且字符串又是我的任務(wù)。。杯具。。
下周三去成都，39h45min，第一次坐這么長時間火車。。
祈禱DSW Chengdu Regional 好運(yùn)。。Regional是如此的寶貴。。不知道以后還有沒有機(jī)會。。