首页 > 代码库 > HDU 4865 Peter's Hobby（概率、dp、log）

HDU 4865 Peter's Hobby（概率、dp、log）

2024-07-13 17:33:04   225人阅读

给出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  }
View Code

 

 

隐马尔可夫模型http://blog.csdn.net/likelet/article/details/7056068


联系
我们