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;
}