首页 > 代码库 > 2014多校第一场 E 题 || HDU 4865 Peter's Hobby （DP）

2014多校第一场 E 题 || HDU 4865 Peter's Hobby （DP）

2024-07-14 01:21:06   242人阅读

题目链接

题意 ： 给你两个表格，第一个表格是三种天气下出现四种湿度的可能性。第二个表格是，昨天出现的三种天气下，今天出现三种天气的可能性。然后给你这几天的湿度，告诉你第一天出现三种天气的可能性，让你求出最可能出现的天气序列 。

思路 ： 定义第 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()的最大值对应的序列就是天气序列。

 

官方题解：

  1 //E  2 #include <cstdio>  3 #include <cstring>  4 #include <vector>  5 #include <iostream>  6 #include <string>  7 #include <algorithm>  8 #include <cmath>  9  10 using namespace std ; 11  12 string str ; 13 vector<int>vec ; 14 double wealea[3][4] = {{0.6,0.2,0.15,0.05},{0.25,0.3,0.2,0.25},{0.05,0.10,0.35,0.50}} ; 15 double weawea[3][3] = {{0.5,0.375,0.125},{0.25,0.125,0.625},{0.25,0.375,0.375}} ; 16 double fir[3] = {0.63,0.17,0.2} ; 17 double dp[53][5] ; 18 double f[53][5] ; 19 int pre[53][5] ; 20 int hum[53] ; 21  22 void solve() 23 { 24     for(int i = 0 ; i < 3 ; i++) 25         fir[i] = log(fir[i]) ; 26     for(int i = 0 ; i < 3 ; i++) 27         for(int j = 0 ; j < 3 ; j ++) 28             weawea[i][j] = log(weawea[i][j]) ; 29 } 30 void Init() 31 { 32     memset(pre,-1,sizeof(pre)) ; 33     memset(f,0,sizeof(f)) ; 34     for(int i = 0 ; i < 53 ; i++) 35         for(int j = 0 ; j < 3 ; j++) 36             dp[i][j] = -9999999 ; 37     vec.clear() ; 38 } 39 int main() 40 { 41     int T, n ; 42     cin >> T ; 43     solve() ; 44     for(int i = 1 ; i <= T ; i++) 45     { 46         cin >> n ; 47         Init() ; 48         for(int j = 0 ; j < n ; j++) 49         { 50             cin >> str ; 51             if(str == "Dry") hum[j] = 0 ; 52             else if(str == "Dryish") hum[j] = 1 ; 53             else if(str == "Damp") hum[j] = 2 ; 54             else if(str == "Soggy") hum[j] = 3 ; 55         } 56         for(int j = 0 ; j < n ; j++) 57         { 58             double x = 0 ; 59             for(int k = 0 ; k < 3 ; k++) 60             { 61                 f[j][k] = wealea[k][hum[j]] ; 62                 x += f[j][k] ; 63             } 64             for(int k = 0 ; k < 3 ; k++) 65                 f[j][k] /= x ; 66         } 67         for(int j = 0 ; j < n  ;j++) 68             for(int k = 0 ; k < 3 ; k++) 69             f[j][k] = log(f[j][k]) ; 70         for(int j = 0 ; j < 3 ; j++) 71             dp[0][j] = f[0][j] + fir[j] ; 72          for(int j = 1 ; j < n ; j ++) 73             for(int k = 0; k < 3 ; k++)//今天 74                 for(int h = 0; h < 3 ; h++)//昨天 75                 { 76                     double x1 = dp[j-1][h]+weawea[h][k]+f[j][k]; 77                     if(dp[j][k] < x1) 78                     { 79                         dp[j][k] = x1; 80                         pre[j][k] = h; 81                     } 82                 } 83         double maxx = -9999999 ; 84         int s = 0,e = n-1 ; 85         for(int j = 0 ; j < 3 ; j++) 86         { 87             if(dp[n-1][j] > maxx) 88             { 89                 maxx = dp[n-1][j] ; 90                 s = j ; 91             } 92         } 93         while(pre[e][s] != -1) 94         { 95             vec.push_back(s) ; 96             s = pre[e][s] ; 97             e -- ; 98         } 99         vec.push_back(s) ;100         cout << "Case #"<<i<<":"<<endl ;101         for(int j = n-1 ; j >= 0 ; j --)102         {103             if(vec[j] == 0) cout<<"Sunny"<<endl ;104             if(vec[j] == 1) cout<<"Cloudy"<<endl ;105             if(vec[j] == 2) cout<<"Rainy"<<endl ;106         }107     }108     return 0 ;109 }
View Code

 


联系
我们