题意 ： 给你两个表格，第一个表格是三种天气下出现四种湿度的可能性。第二个表格是，昨天出现的三种天气下，今天出现三种天气的可能性。然后给你这几天的湿度，告诉你第一天出现三种天气的可能性，让你求出最可能出现的天气序列 。
思路 ： 定义第 i 天叶子湿度为hum[i]。第 i 天，天气为 j 的最大概率为dp[i][j]。wealea[i][j]表示天气为 i 叶子为j的概率，weawea[i][j]表示今天天气为 i 明天天气为j的概率，st[i]表示第一天天气为i的概率。pre[i][j]: 第i天，天气为j时，前一天最可能的天气 。fir[i]表示第1天天气为 i 的概率。
对于存在的叶子序列{a1,a2......an},存在一个天气序列{b1,b2......bn}，那么总的概率dp[n][j]=max(fir[b1]*wealea[b1][a1]*weawea[b1][b2]*wealea[b2][a2]*......* weawea[bn-1][bn]*wealea[bn][an])。数据太小可能会丢失精度，所以可以用log将乘法转化成加法，即log()=log(fir[b1])+log(wealea[b1][a1])+log(weawea[b1][b2])+log(wealea[b2][a2])+......+log(weawea[bn-1][bn])+log(wealea[bn][an])。求log()的最大值对应的序列就是天气序列。
官方题解：
//E
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath> using namespace std ; string str ;
vector<int>vec ;
double wealea[][] = {{0.6,0.2,0.15,0.05},{0.25,0.3,0.2,0.25},{0.05,0.10,0.35,0.50}} ;
double weawea[][] = {{0.5,0.375,0.125},{0.25,0.125,0.625},{0.25,0.375,0.375}} ;
double fir[] = {0.63,0.17,0.2} ;
double dp[][] ;
double f[][] ;
int pre[][] ;
int hum[] ; void solve()
{
for(int i = ; i < ; i++)
fir[i] = log(fir[i]) ;
for(int i = ; i < ; i++)
for(int j = ; j < ; j ++)
weawea[i][j] = log(weawea[i][j]) ;
}
void Init()
{
memset(pre,-,sizeof(pre)) ;
memset(f,,sizeof(f)) ;
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
dp[i][j] = - ;
vec.clear() ;
}
int main()
{
int T, n ;
cin >> T ;
solve() ;
for(int i = ; i <= T ; i++)
{
cin >> n ;
Init() ;
for(int j = ; j < n ; j++)
{
cin >> str ;
if(str == "Dry") hum[j] = ;
else if(str == "Dryish") hum[j] = ;
else if(str == "Damp") hum[j] = ;
else if(str == "Soggy") hum[j] = ;
}
for(int j = ; j < n ; j++)
{
double x = ;
for(int k = ; k < ; k++)
{
f[j][k] = wealea[k][hum[j]] ;
x += f[j][k] ;
}
for(int k = ; k < ; k++)
f[j][k] /= x ;
}
for(int j = ; j < n ;j++)
for(int k = ; k < ; k++)
f[j][k] = log(f[j][k]) ;
for(int j = ; j < ; j++)
dp[][j] = f[][j] + fir[j] ;
for(int j = ; j < n ; j ++)
for(int k = ; k < ; k++)//今天
for(int h = ; h < ; h++)//昨天
{
double x1 = dp[j-][h]+weawea[h][k]+f[j][k];
if(dp[j][k] < x1)
{
dp[j][k] = x1;
pre[j][k] = h;
}
}
double maxx = - ;
int s = ,e = n- ;
for(int j = ; j < ; j++)
{
if(dp[n-][j] > maxx)
{
maxx = dp[n-][j] ;
s = j ;
}
}
while(pre[e][s] != -)
{
vec.push_back(s) ;
s = pre[e][s] ;
e -- ;
}
vec.push_back(s) ;
cout << "Case #"<<i<<":"<<endl ;
for(int j = n- ; j >= ; j --)
{
if(vec[j] == ) cout<<"Sunny"<<endl ;
if(vec[j] == ) cout<<"Cloudy"<<endl ;
if(vec[j] == ) cout<<"Rainy"<<endl ;
}
}
return ;
}