HDU 4865

Peter’s Hobby

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 344 Accepted Submission(s): 148

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

Source

2014 Multi-University Training Contest 1

马尔科夫链去转移，记录路径，然后输出结果。

/* ***************

Author        :kuangbin

Created Time  :2014/7/23 21:58:58

File Name     :E:\2014ACM\比赛\2014多校训练\2014多校1\HDU4865.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

double dp[100][3];

int pre[100][3];

char str[20];

double a[][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 b[][3] = 

{

	{0.5,0.375,0.125},

	{0.25,0.125,0.625},

	{0.25,0.375,0.375},

};

int get(char str[])

{

	if(strcmp(str,"Dry") == 0)return 0;

	else if(strcmp(str,"Dryish") == 0)return 1;

	else if(strcmp(str,"Damp") == 0)return 2;

	else return 3;

}

void out(int i,int t)

{

	if(i > 1)out(i-1,pre[i][t]);

	if(t == 0)printf("Sunny\n");

	else if(t == 1)printf("Cloudy\n");

	else printf("Rainy\n");

}

int main()

{

   // freopen("1005.in","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int iCase = 0;

	int n;

	scanf("%d",&T);

	while(T--)

	{

		iCase++;

		scanf("%d",&n);

		printf("Case #%d:\n",iCase);

		dp[0][0] = log(0.63);

		dp[0][1] = log(0.17);

		dp[0][2] = log(0.2);

		for(int i = 1;i <= n;i++)

		{

			scanf("%s",str);

			int id = get(str);

			if(i == 1)

			{

				for(int j = 0;j < 3;j++)

					dp[i][j] = dp[i-1][j] + log(a[j][id]);

			}

			else

			{

				for(int j = 0;j < 3;j++)

				{

					dp[i][j] = -100000000.0;

					for(int t = 0;t < 3;t++)

					{

						if(dp[i-1][t] + log(b[t][j])+log(a[j][id]) > dp[i][j])

						{

							dp[i][j] = dp[i-1][t]+log(b[t][j])+log(a[j][id]);

							pre[i][j] = t;

						}

					}

				}

			}

		}

		if(dp[n][0] > dp[n][1] && dp[n][0] > dp[n][2])

			out(n,0);

		else if(dp[n][1] > dp[n][0] && dp[n][1] > dp[n][2])

			out(n,1);

		else out(n,2);

	}

    return 0;

}