hdu 4865 Peter's Hobby（機率dp）

http://acm.hdu.edu.cn/showproblem.php?pid=4865

大緻題意：有三種天氣和四種葉子狀态。給出兩個表，分别是每種天氣下葉子呈現狀态的機率和今天天氣對明天天氣的機率。給出n天葉子的狀态，輸出最有可能的天氣序列。

思路：wl[i][j]表示天氣為i，葉子為j的機率，ww[i][j]表示今天天氣為i明天天氣為j的機率，st[i]表示第一天天氣為i的機率。

對于葉子序列{a1,a2......an},存在一個天氣序列{b1,b2......bn}，那麼總的機率g[n]=st[b1]*wl[b1][a1]*ww[b1][b2]*wl[b2][a2]*......*ww[bn-1][bn]*wl[bn][an]。即log(g[n])=log(st[b1])+log(wl[b1][a1])+log(ww[b1][b2])+log(wl[b2][a2])+......+log(ww[bn-1][bn])+log(wl[bn][an])。求log(g[n])的最大值對應的序列就是天氣序列。

相當于給一個n*3的矩陣，代表有n天，每天有3種天氣，從第一行到第n行求出一條最長路，輸出路徑。

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;

const int INF = 0x3f3f3f3f;
double wl[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 ww[3][3] = {
{0.5,0.375,0.125},
{0.25,0.125,0.625},
{0.25,0.375,0.375}
};

double st[3] = {0.63,0.17,0.2};
int n;
char s[10];
int a[55];
double f[55][5];
double dp[55][5];
int pre[55][5];

stack <int> sta;

int init(char s[])
{
	if(strcmp(s,"Dry") == 0)
		return 0;
	if(strcmp(s,"Dryish") == 0)
		return 1;
	if(strcmp(s,"Damp") == 0)
		return 2;
	if(strcmp(s,"Soggy") == 0)
		return 3;
}

void To()
{
	for(int i = 0; i < 3; i++)
	{
		for(int j = 0; j < 3; j++)
			ww[i][j] = log(ww[i][j]);
	}
	for(int i = 0; i < 3; i++)
		st[i] = log(st[i]);
}

int main()
{
	To();
	int test;
	scanf("%d",&test);
	for(int item = 1; item <= test; item++)
	{
		scanf("%d",&n);
		memset(pre,-1,sizeof(pre));
		memset(f,0,sizeof(f));
		for(int i = 1; i <= n; i++)
		{
			scanf("%s",s);
			a[i] = init(s);
		}

		for(int i = 1; i <= n; i++)
		{
			//對于目前天的葉子狀态是固定的，現在的f[i][j]表示第i天在葉子固定的條件下天氣為j的機率，
			//是以f[i][j]為每種天氣占總天氣的比值
			double t = 0;
			for(int j = 0; j < 3; j++)
			{
				f[i][j] = wl[j][a[i]];
				t += wl[j][a[i]];
			}
			for(int j = 0; j < 3; j++)
				f[i][j] /= t;
		}

		for(int i = 1; i <= n; i++)
		{
			for(int j = 0; j < 3; j++)
				f[i][j] = log(f[i][j]);
		}
		memset(dp,-INF,sizeof(dp));
		for(int j = 0; j < 3; j++)
			dp[1][j] = st[j] + f[1][j];

		for(int i = 2; i <= n; i++)
		{
			for(int j = 0; j < 3; j++)
			{
				for(int k = 0; k < 3; k++)
				{
					double t = dp[i-1][k] + ww[k][j] + f[i][j];
					if(dp[i][j] < t)
					{
						dp[i][j] = t;
						pre[i][j] = k;
					}
				}
			}
		}
		int p = n;
		int c;
		double Max = -INF;

		for(int j = 0; j < 3; j++)
		{
			if(dp[n][j] > Max)
			{
				Max = dp[n][j];
				c = j;
			}
		}

		while(!sta.empty()) sta.pop();

		sta.push(c);
		while(pre[p][c] != -1)
		{
			sta.push(pre[p][c]);
			c = pre[p][c];
			p--;
		}

		printf("Case #%d:\n",item);
		while(!sta.empty())
		{
			if(sta.top() == 0)
				printf("Sunny\n");
			if(sta.top() == 1)
				printf("Cloudy\n");
			if(sta.top() == 2)
				printf("Rainy\n");
			sta.pop();
		}
	}
	return 0;
}