hdu4865Peter's Hobby马尔科夫过程

#include<iostream>
#include<string>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
double p1[3][4]={0.6,0.2,0.15,0.05,0.25,0.3,0.2,0.25,0.05,0.1,0.35,0.5};
double p2[3][3]={0.5,0.375,0.125,0.25,0.125,0.625,0.25,0.375,0.375};
double fu[50][3]={log(0.63),log(0.17),log(0.2)},pre[50][3];
map<string,int>m1;
map<int,string>m2;
void init()
{
	m1.insert(make_pair("Dry",0));
	m1.insert(make_pair("Dryish",1));
	m1.insert(make_pair("Damp",2));
	m1.insert(make_pair("Soggy",3));
	m2.insert(make_pair(0,"Sunny"));
	m2.insert(make_pair(1,"Cloudy"));
	m2.insert(make_pair(2,"Rainy"));
}
void work()
{
	double t,tt,ttt;
	int n,i,j,k,x,y,r;
	string s;
	cin>>n;

	cin>>s;
	i=m1[s];
	for(j=0;j<3;j++)
		fu[0][j]=fu[0][j]+log(p1[j][i]);
	
	for(i=1;i<n;i++)
	{
		cin>>s;
		y=i-1;
		j=m1[s];
		for(k=0;k<3;k++)
		{
			t=log(0);
			for(x=0;x<3;x++)
			{
				tt=fu[y][x]+log(p2[x][k])+log(p1[k][j]);
				if(t<tt)
				{
					t=tt;
					r=x;
				}
			}
			pre[i][k]=r;
			fu[i][k]=t;
		}
	}
	
	t=log(0);
	i=n-1;
	for(j=0;j<3;j++)
		if(t<fu[i][j])
		{
			t=fu[i][j];
			r=j;
		}
		
	vector<int>v;
	v.push_back(r);
	for(i=n-1;i>0;i--)
	{
		v.push_back(pre[i][r]);
		r=pre[i][r];
	}
	for(i=n-1;i>-1;i--)
		cout<<m2[v[i]]<<endl;
}
int main()
{
	int exp,i;
	init();
	cin>>exp;
	for(i=1;i<=exp;i++)
	{
		printf("Case #%d:\n",i);
		work();
	}
}