hdu多校聯合Peter's Hobby

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.
   
    
        

 開始想得太簡單，是按照得到每一天的樹葉狀況來找到使之機率最大的天氣，後來看到讨論裡說是求機率最大的天氣序列。hint後來又說log這個函數是有用的T0T，難道這道題用到了log函數？？？太多不明白了，而且直到比賽結束也沒能想明白怎麼的最大機率序列法……

看了題解，沒有什麼log……動态規劃，從第一天算起，到最後一天。dp[i][j]代表第i天天氣為j的最大機率(j從0到3)，就等于dp[i-1][k]*P2[k][j]*P1[j][t_leave[i]](k從0到3)的最大值。用一個數組記錄每次最大機率選的的天氣标号。

#include<cstdio>
#include<cstring>

int ans[55];
int t_leave[55];
int flag[55][55];
double dp[55][55];
char weather[3][10]= {"Sunny","Cloudy","Rainy"};
char leave[4][10]= {"Dry","Dryish","Damp","Soggy"};
double P1[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};
double P2[3][3]= {0.5,0.375,0.125,0.25,0.125,0.625,0.25,0.375,0.375};

void deal(int a,int b)
{
    int i,t;
    double Max=-1,tmp;
    for(i=0; i<3; i++)
    {
        tmp=dp[a-1][i]*P2[i][b]*P1[b][t_leave[a]];
        if(Max<tmp)
        {
            Max=tmp;
            t=i;
        }
    }
    dp[a][b]=Max;
    flag[a][b]=t;
}

int main()
{
    char str[10];
    int T,t,n,i,j,k;
    scanf("%d",&T);
    for(t=1;t<=T;t++)
    {
        scanf("%d",&n);
        for(i=1; i<=n; i++)
        {
            scanf("%s",str);
            for(j=0; j<4; j++)
                if(strcmp(str,leave[j])==0)
                {
                    t_leave[i]=j;
                    break;
                }
        }
        memset(dp,0,sizeof(dp));
        dp[1][0]=0.63*P1[0][t_leave[1]];
        dp[1][1]=0.17*P1[1][t_leave[1]];
        dp[1][2]=0.2*P1[2][t_leave[1]];
        for(i=2; i<=n; i++)
            for(j=0; j<3; j++)
                deal(i,j);
        /*for(i=2;i<=n;i++)
        {
			for(j=0;j<3;j++)
        		printf("%d ",flag[i][j]);
        	printf("\n");
		}*/
        j=k=0;
        for(i=0; i<3; i++)
            if(dp[n][i]>dp[n][k])k=i;//找到機率最大的天氣序列 
        ans[j++]=k;
        for(i=n-1; i>=1; i--)
        {
            k=flag[i+1][k];
            ans[j++]=k;
        }
        printf("Case #%d:\n",t);
        for(i=j-1;i>=0;i--)
            printf("%s\n",weather[ans[i]]);
    }
    return 0;
}