HDU 4865 Peter's Hobby(輸出路徑的dp)

這道題最主要的是要按照它的提示:Log is useful.把求對數乘法轉化為求對數的加法，然後求出最大值。輸出路徑。

對于一個天氣序列存在的機率為：

st[a1]*w_h[a1][b1]* w_w[a1][a2] *w_h[a2][b2]* w_w[a2][a3]* w_h[a3][b3]*........*w_w[an-1][an]*w_h[an][bn];

其中：

葉子的狀态序列為{b1,b2...bn}

那麼對于某個天氣序列｛a1,a2....an}

這裡用的是連乘，轉化為log之後可以化簡為log( st[a1]*w_h[a1][b1]* w_w[a1][a2] *w_h[a2][b2]* w_w[a2][a3]* w_h[a3][b3]*........*w_w[an-1][an]*w_h[an][bn]) = log( st[a1]*w_h[a1][b1]* w_w[a1][a2] *)+........+log( w_w[an-1][an]*w_h[an][bn]).

這樣的話就可以從第一天開始找一條機率最大路徑然後列印出天氣就行了啊。

這題vector忘了清空錯了好幾次，得注意！！！

Peter's Hobby

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 182    Accepted Submission(s): 80

Problem Description Recently, Peter likes to measure the humidity of leaves. He recorded a leaf humidity every day. There are four types of leaves wetness: Dry , Dryish , Damp and Soggy. As we know, the humidity of leaves is affected by the weather. And there are only three kinds of weather: Sunny, Cloudy and Rainy.For example, under Sunny conditions, the possibility of leaves are dry is 0.6.

Give you the possibility list of weather to the humidity of leaves.

The weather today is affected by the weather yesterday. For example, if yesterday is Sunny, the possibility of today cloudy is 0.375.

The relationship between weather today and weather yesterday is following by table:

Now,Peter has some recodes of the humidity of leaves in N days.And we know the weather conditons on the first day : the probability of sunny is 0.63,the probability of cloudy is 0.17,the probability of rainny is 0.2.Could you know the weathers of these days most probably like in order?  

Input The first line is T, means the number of cases, then the followings are T cases. for each case:

The first line is a integer n(n<=50),means the number of days, and the next n lines, each line is a string shows the humidity of leaves (Dry, Dryish, Damp, Soggy)  

Output For each test case, print the case number on its own line. Then is the most possible weather sequence.( We guarantee that the data has a unique solution)  

Sample Input

1
3
Dry
Damp
Soggy
        

Sample Output

Case #1:
Sunny
Cloudy
Rainy


   
    
     Hint
    Log is useful.
   
    
        

Author FZU

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-6
///#define M 1000100
#define LL __int64
///#define LL long long
#define INF 0x7fffffff
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

const int maxn = 210;

using namespace std;

double w_w[3][3] =
{
    {0.5,0.375,0.125},
    {0.25,0.125,0.625},
    {0.25,0.375,0.375}
};

double w_h[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.5}
};

double st[3] = {0.63,0.17,0.2};

double dp[maxn][maxn];
double f[maxn][maxn];
char str[maxn];
int pre[maxn][maxn];
int num[maxn];
int n;
vector<int>g;
void Del()
{
    for(int i = 0; i < 3; i++)
        st[i] = log(st[i]);
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            w_w[i][j] = log(w_w[i][j]);
}

void init()
{
    g.clear();
    memset(pre, -1, sizeof(pre));
    memset(f, 0, sizeof(f));
    for(int i = 0; i <= n; i++)
        for(int j = 0; j < 3; j++)
            dp[i][j] = -INF;
}

int main()
{
    Del();
    int T;
    int Case = 1;
    cin >>T;
    while(T--)
    {
        scanf("%d",&n);
        init();
        for(int i = 1; i <= n; i++)
        {
            scanf("%s",str);
            if(!strcmp(str, "Dry")) num[i] = 0;
            else if(!strcmp(str, "Dryish")) num[i] = 1;
            else if(!strcmp(str, "Damp")) num[i] = 2;
            else if(!strcmp(str, "Soggy")) num[i] = 3;
        }
        for(int i = 1; i <= n; i++)
        {
            double s = 0;
            for(int j = 0; j < 3; j++)
            {
                f[i][j] = w_h[j][num[i]];
                s += f[i][j];
            }
            for(int j = 0; j < 3; j++) f[i][j] /= s;
        }
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 3; j++)
                f[i][j] = log(f[i][j]);
        for(int i = 0; i < 3; i++)
            dp[1][i] = f[1][i]+st[i];
        for(int i = 2; i <= n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                for(int k = 0; k < 3; k++)
                {
                    double ss = dp[i-1][k]+w_w[k][j]+f[i][j];
                    if(dp[i][j] < ss)
                    {
                        dp[i][j] = ss;
                        pre[i][j] = k;
                    }
                }
            }
        }
        double Max = -INF;
        int s = 0;
        int p = n;
        for(int i = 0; i < 3; i++)
        {
            if(Max < dp[n][i])
            {
                Max = dp[n][i];
                s = i;
            }
        }
        while(pre[p][s] != -1)
        {
            g.push_back(s);
            s = pre[p][s];
            p--;
        }
        g.push_back(s);
        cout<<"Case #"<<Case++<<":"<<endl;
        for(int i = n-1; i >= 0; i--)
        {
            if(g[i]==0) puts("Sunny");
            if(g[i]==1) puts("Cloudy");
            if(g[i]==2) puts("Rainy");
        }
    }
    return 0;
}