首页 > 代码库 > HDU 4865 Peter's Hobby(概率、dp、log)
HDU 4865 Peter's Hobby(概率、dp、log)
给出2个影响矩阵,一个是当天天气对湿度的影响,一个是前一天天气对当天天气的影响。
即在晴天(阴天、雨天)发生Dry(Dryish、Damp、Soggy)的概率,以及前一天晴天(阴天、雨天)而今天发生晴天(阴天、雨天)的概率。
其中第一天的晴天阴天雨天概率为0.63,0.17,0.20
输入n天的湿度情况,输出最有可能的n天的天气。
用dp[i][j]表示第i天为j天气的概率,用pre[i][j]表示它的前驱。
注意由于概率相乘次数过多,要用log放大。。不然会接近0、精度不够、误差大
dp[i][j] = max{dp[i-1][k] + w_w[k][j] + w_h[j][h[i]]},当然这些w_w, w_h要全部都log
w_w[k][j]表示昨天k天气今天j天气的概率,w_h[j][h[i]]表示今天j天气发生h[i]湿度的概率
这样出来的dp[i][j]就可以表示第i天为j天气,且湿度为h[i] 。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 using namespace std; 6 7 double aa[3][4]={ 8 0.6, 0.2, 0.15, 0.05, 9 0.25, 0.3, 0.2, 0.25,10 0.05, 0.10, 0.35, 0.5011 };12 double bb[3][3]={13 0.5, 0.375, 0.125,14 0.25, 0.125, 0.625,15 0.25, 0.375, 0.37516 };17 int main(){18 for(int i=0;i<3;++i)for(int j=0;j<4;++j) aa[i][j] = log(aa[i][j]);19 for(int i=0;i<3;++i)for(int j=0;j<3;++j) bb[i][j] = log(bb[i][j]);20 int t,n,lea[55],ca=0;21 double dp[55][3];22 int pre[55][3];23 int ans[55];24 scanf("%d",&t);25 while(t--){26 scanf("%d",&n);27 for(int i=0;i<n;++i){28 char s[22];29 scanf("%s",s);30 if(strcmp(s,"Dry")==0) lea[i]=0;31 else if(strcmp(s,"Dryish")==0) lea[i]=1;32 else if(strcmp(s,"Damp")==0) lea[i]=2;33 else lea[i]=3;34 }35 dp[0][0] = log(0.63)+aa[0][lea[0]];36 dp[0][1] = log(0.17)+aa[1][lea[0]];37 dp[0][2] = log(0.20)+aa[2][lea[0]];38 for(int i=1;i<n;++i){39 for(int j=0;j<3;++j){40 double ma = -1e8; int idx;41 for(int k=0;k<3;++k){42 if(dp[i-1][k]+bb[k][j]+aa[j][lea[i]] >ma){43 ma = dp[i-1][k]+bb[k][j]+aa[j][lea[i]];44 idx = k;45 }46 }47 dp[i][j] = ma, pre[i][j]=idx;48 }49 }50 double ma=-1e8;int idx;51 for(int j=0;j<3;++j)if(dp[n-1][j]>ma){ma=dp[n-1][j];idx=j;}52 ans[n-1]=idx;53 for(int i=n-1;i;--i){54 ans[i-1] = pre[i][idx];55 idx = pre[i][idx];56 }57 printf("Case #%d:\n",++ca);58 for(int i=0;i<n;++i){59 if(ans[i]==0)puts("Sunny");60 else if(ans[i]==1)puts("Cloudy");61 else puts("Rainy");62 }63 }64 return 0;65 }
隐马尔可夫模型http://blog.csdn.net/likelet/article/details/7056068
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。