学步园

由数据给出的形式，推得题目原型是这样一个模型——隐马尔科夫模型。

样例推导过程应该是这样的

每一天的天气组成都可以由前一天的天气组成推出，而由当天叶片湿度现象，可以倒推出当天最有可能的天气（解码）。
把整个题目情景作为一个马尔科夫过程，那么可知的是：天气的初始状态，每一天的叶片状态（观测状态）。题目要求求出最有可能的天气顺序（隐藏状态）。可以写出三个矩阵：

初始状态概率矩阵 

隐含状态概率转移矩阵 

观测状态概率放射矩阵

有了上面的推论，可以得出几点：
1.当前的隐藏状态天气组成s(i)和观测状态o(i)都只与前一天隐藏状态天气组成s(i-1)有关，而与在此之前所有的隐藏状态或是观测状态均无直接关系；
2.由一个初始隐藏状态天字组成s(1)、一个隐含状态概率转移矩阵和一个观测状态概率放射矩阵，可以得到任意一天的隐藏状态天气组成s(i)(i >= 1)；
3.由当前观测状态o(i)、观测状态概率放射矩阵和上一次的隐藏状态天气组成s(i-1)，通过最大似然估计法，可以倒推出隐藏状态天气组成s(i-1)中最有可能显现的状态（但最后一天是直接由概率推出状态）。

最大似然估计法：
并且在x的所有取值上，使似然函数的值最大化(一阶导数为0)，即这个使可能性最大的x0值即被称为x的最大似然估计。

有了上面几个特点，发现这种算法是一种DP，状态转移方程（摘自维基百科）：

相关链接：

[转载]发现一篇不错的学习隐马尔可夫模型的文章
http://blog.sciencenet.cn/blog-641976-533895.html
维特比算法 - 维基百科
http://zh.wikipedia.org/wiki/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95
HMM学习笔记_3(从一个实例中学习Viterbi算法)
http://www.cnblogs.com/tornadomeet/archive/2012/03/24/2415889.html
最大似然估计 - 维基百科
http://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <assert.h>
#include <algorithm>
#define MAX 1234567890
#define MIN -1234567890
#define eps 1e-8
#define HIDSUM 3
#define OBSSUM 4
#define N 51

using namespace std;

///初始状态概率
double pi[HIDSUM] = {0.63, 0.17, 0.2};

///隐含状态概率转移矩阵
double A[HIDSUM][HIDSUM] = {
        {0.5,  0.375, 0.125},
        {0.25, 0.125, 0.625},
        {0.25, 0.375, 0.375}
};

///观测状态概率放射矩阵
double B[HIDSUM][OBSSUM] = {
        {0.6,  0.2,  0.15, 0.05},
        {0.25, 0.3,  0.2,  0.25},
        {0.05, 0.10, 0.35, 0.50}
};

char O[OBSSUM][10] = {"Dry", "Dryish", "Damp",  "Soggy"};
char S[HIDSUM][10] = {"Sunny", "Cloudy", "Rainy"};

///dp[t][k]：第t天，最后状态落在S[k]观察到obs_seq[t]的最大概率
double dp[N][HIDSUM];
int rec[N][HIDSUM];

int obs_seq[N];
int hid_seq[N];

int n;

void Viterbi()
{
        int i, j, k;

        ///初始化第一天
        for(k = 0; k < HIDSUM; k++)
        {
                dp[0][k] = log(pi[k]) + log(B[k][obs_seq[0]]);
                rec[0][k] = k;
        }

        for(i = 1; i < n; i++)
        {
                for(j = 0; j < HIDSUM; j++)
                {
                        dp[i][j] = MIN;
                        for(k = 0; k < HIDSUM; k++)
                        {
                                ///从昨天的三个状态过来，分别通过隐含状态概率矩阵转换，
                                ///于是今天的每个状态都有三个概率，再对这九个概率，
                                ///通过观测状态概率放射矩阵，
                                ///求出每个隐含状态下该观测状态的最大概率，
                                ///并记录在此情况下的上一次的隐含状态
                                double tmp = dp[i-1][k] + log(A[k][j]) + log(B[j][obs_seq[i]]);
                                if(tmp > dp[i][j])
                                {
                                        dp[i][j] = tmp;
                                        rec[i][j] = k;
                                }
                        }
                }
        }

        double last = MIN;
        for(k = 0; k < HIDSUM; k++)
        {
                if(dp[n-1][k] > last)
                {
                        last = dp[n-1][k];
                        hid_seq[n-1] = k;
                }
        }

        for(i = n - 2; i >= 0; i--)
        {
                hid_seq[i] = rec[i+1][hid_seq[i+1]];
        }
}

int check(char *o)
{
        for(int s = 0; s < OBSSUM; s++)
        {
                if(strcmp(o, O[s]) == 0) return s;
        }
}

int main()
{
//        freopen("data.in", "r", stdin);

        int t;
        scanf("%d", &t);

        for(int m = 1; m <= t; m++)
        {
                scanf("%d", &n);
                getchar();

                for(int d = 0; d < n; d++)
                {
                        char leaf[10];
                        gets(leaf);
                        obs_seq[d] = check(leaf);
                }

                Viterbi();

                printf("Case #%d:\n", m);
                for(int d = 0; d < n; d++) {printf("%s\n", S[hid_seq[d]]);}
        }

        return 0;
}