题意：已知昨天天气与今天天气状况的概率关系（wePro），和今天天气状态和叶子湿度的概率关系(lePro)

第一天为sunny 概率为 0.63,cloudy 概率 0.17,rainny 概率 0.2.

给定n天的叶子湿度状态，求这n天最可能的天气情况

分析：概率dp

设 dp[i][j] 表示第i天天气为j的最大概率，

pre[i][j]表示第i天天气最可能为j的前一天天气，

dp[i][j]=max(dp[i-1][k]+log(wePro[k][j])+log(lePro[j][lePos[i]])) (k=0,1,2 表示昨天的天气）

注：由于概率越乘越小，考虑精度原因，用log取对数

log(a*b*c) = log a + log b +log c

1 #include
     
       2 #include
      
        3 #include
       
         4 char yezi[5][10]= {
   "Dry","Dryish","Damp","Soggy"}; 5 char wea[4][10]= {
   "Sunny","Cloudy","Rainy"}; 6 double yeP[3][4]= {
   0.6,0.2,0.15,0.05, 7                    0.25,0.3,0.2,0.25, 8                    0.05,0.10,0.35,0.50 9                   };10 double weaP[3][3]= {
   0.5,0.375,0.125,11                     0.25,0.125,0.625,12                     0.25,0.375,0.37513                    };14 double init[3]= {
   0.63,0.17,0.2};15 double dp[51][3],pre[51][3];16 int n;17 double maxp;18 int Pos[51];19 void solve()20 {21     for(int i=0; i<3; i++)22     {23         dp[1][i]=log(init[i])+log(yeP[i][Pos[1]]);24                  //第1天天气为i的概率=初始的天气为i的概率*（第一天叶子为Pos[1]的的状态下天气为i的概率）25     }26     for(int i=2; i<=n; i++) //27     {28         for(int j=0; j<3; j++) //天气29         {30             double maxp=-1e8;31             int pos=0;//记录天气32             for(int k=0; k<3; k++) //第i-1天天气为k33             {34                 double temp=dp[i-1][k]+log(weaP[k][j])+log(yeP[j][Pos[i]]);35                 //昨天天气为k的概率*昨天天气为k今天天气为j的概率*叶子状态为Pos[i]时天气为j的概率36                 if(temp>maxp)37                 {38                     maxp=temp;39                     pos=k;//记录最有可能的天气状况为k40                 }41             }42             dp[i][j]=maxp;//第i天天气状况为j的概率43             pre[i][j]=pos; //表示第i天天气最可能为j的前一天天气44         }45     }46 }47 int main()48 {49     int k=0;50     int T;51     char yeC[10];52     scanf("%d",&T);53     while(T--)54     {55         k++;56         printf("Case #%d:\n",k);57         scanf("%d",&n);58         for(int i=1; i<=n; i++)59         {60             scanf("%s",yeC);61             for(int j=0; j<4; j++)62                 if(strcmp(yeC,yezi[j])==0)63                 {64                     Pos[i]=j;65                     break;66                 }67         }68         solve();69         double maxp=-1e8;70         int ans[51];71         for(int i=0; i<3; i++)//第n天最有可能的天气72             if(dp[n][i]>maxp)73             {74                 maxp=dp[n][i];75                 ans[n]=i;76             }77          for(int i=n-1;i>=1;i--)78             ans[i]=pre[i+1][ans[i+1]];  //由最后一天往前找每天的天气状况记录在ans 中79         for(int i=1;i<=n;i++)80             printf("%s\n",wea[ans[i]]);81     }82     return 0;83 }
       
      
     

资料扩展：

本题属于 隐马尔可夫模型

马尔可夫模型:统计模型，每个状态只依赖于之前的状态

马尔可夫模型可用马尔可夫过程描述

我们就为上面的一阶马尔科夫过程定义了以下三个部分：

　　状态：晴天、阴天和下雨

　　初始向量：定义系统在时间为0的时候的状态的概率

　　状态转移矩阵：每种天气转换的概率

　　所有的能被这样描述的系统都是一个马尔科夫过程。

隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。

包含隐藏状态 （如：天气状态）和 可观状态（如：叶子的湿度）

可以观察到的状态序列和隐藏的状态序列是概率相关的