hdu 4865 Peter's Hobby(DP)

제목: n일의 습도를 주고 확률이 가장 높은 n일의 날씨를 추측한다.i일째 날씨는 i+1일째 날씨에 영향을 주고 i일째 날씨는 이날의 습도에 영향을 주며 확률은 표에서 제시한다.
사고방식: 직접 dp를 하고 경로를 구하면 된다. dp[i][j]는 전날 i일이 모두 요구를 만족시켰고 다음날 날씨가 j일 확률을 나타낸다.전이 방정식을 모두 곱해야 하기 때문에 계산 과정의 중치가 매우 작을 수 있기 때문에 나는 log로 계산했다. 그러나 쓰지 않아도 된다. 한참을 웅크리고 나서야 단어를 잘못 베낀 것을 발견하고 어리석게 울었다.
코드:

#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL;
using namespace std;
typedef long long ll;
const int maxn=55;
double p[3][3]={{0.5,0.375,0.125},
                {0.25,0.125,0.625},
                {0.25,0.375,0.375}
                };
double q[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}
                };
char * weather[3]={(char*)"Sunny",(char*)"Cloudy",(char*)"Rainy"};
double dp[maxn][3];
int x[maxn],pa[maxn][3],ans[maxn];
int getx(char * s)
{
    if(strcmp(s,"Dry")==0) return 0;
    if(strcmp(s,"Dryish")==0) return 1;
    if(strcmp(s,"Damp")==0) return 2;
    return 3;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    char str[10];
    int t,tcase=0,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%s",str);
            x[i]=getx(str);
        }
        for(int i=1;i<=n;++i)
            for(int j=0;j<3;++j)
                dp[i][j]=log(0);
        memset(pa,0,sizeof(pa));
        dp[1][0]=log(0.63)+log(q[0][x[1]]);
        dp[1][1]=log(0.17)+log(q[1][x[1]]);
        dp[1][2]=log(0.20)+log(q[2][x[1]]);
        for(int i=2;i<=n;++i)
        {
            for(int j=0;j<3;++j)
            {
                for(int k=0;k<3;++k)
                {
                    double tmp=dp[i-1][k]+log(p[k][j])+log(q[j][x[i]]);
                    if(tmp>dp[i][j])
                    {
                        dp[i][j]=tmp;
                        pa[i][j]=k;
                    }
                }
            }
        }
        int pos=0;
        for(int i=0;i<3;++i)
            if(dp[n][i]>dp[n][pos]) pos=i;
        ans[n]=pos;
        for(int i=n-1;i>=1;--i)
        {
            pos=pa[i+1][pos];
            ans[i]=pos;
        }
        printf("Case #%d:
",++tcase);
        for(int i=1;i<=n;++i)
            printf("%s
",weather[ans[i]]);
    }
    return 0;
}