$dp$。
这题的本质和求一个有向无环图的最长路径长度的路径是一样的。
$dp[i][j]$表示到第$i$天，湿度为$a[i]$，是第$j$种天气的最大概率。记录一下最大概率是$i-1$天哪一种天气推过来的，然后就可以得到路径了。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<ctime>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c = getchar();
x = ;
while(!isdigit(c)) c = getchar();
while(isdigit(c))
{
x = x * + c - '';
c = getchar();
}
} double ts[][]={
{ ,,,,},
{ , 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 tt[][]={
{ , , },
{ , 0.5, 0.375, 0.125 },
{ , 0.25, 0.125, 0.625 },
{ , 0.25, 0.375, 0.375 },
};
double dp[][];
int T,n,p[][],a[],cas=; int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
char s[]; scanf("%s",s);
if(strcmp(s,"Dry")==) a[i]=;
else if(strcmp(s,"Dryish")==) a[i]=;
else if(strcmp(s,"Damp")==) a[i]=;
else a[i]=;
} memset(p,-,sizeof p);
memset(dp,,sizeof dp); dp[][]=ts[][a[]]*0.63;
dp[][]=ts[][a[]]*0.17;
dp[][]=ts[][a[]]*0.2; for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
{
for(int k=;k<=;k++)
{
if(dp[i-][k]*tt[k][j]*ts[j][a[i]]>dp[i][j])
{
dp[i][j]=dp[i-][k]*tt[k][j]*ts[j][a[i]];
p[i][j]=k;
}
}
}
} stack<int>S; double mx=; int idx=;
for(int j=;j<=;j++) if(dp[n][j]>mx) mx=dp[n][j],idx=j; int now=idx, r=n;
while()
{
S.push(now);
now=p[r][now];
r--;
if(now==-) break;
} printf("Case #%d:\n",cas++);
while(!S.empty())
{
int x=S.top(); S.pop();
if(x==) printf("Sunny\n");
else if(x==) printf("Cloudy\n");
else printf("Rainy\n");
} }
return ;
}