首页 > 代码库 > HDU 4865 Peter's Hobby
HDU 4865 Peter's Hobby
Peter‘s Hobby
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 647 Accepted Submission(s): 273
Problem Description
Recently, Peter likes to measure the humidity of leaves. He recorded a leaf humidity every day. There are four types of leaves wetness: Dry , Dryish , Damp and Soggy. As we know, the humidity of leaves is affected by the weather. And there are only three kinds of weather: Sunny, Cloudy and Rainy.For example, under Sunny conditions, the possibility of leaves are dry is 0.6. Give you the possibility list of weather to the humidity of leaves. The weather today is affected by the weather yesterday. For example, if yesterday is Sunny, the possibility of today cloudy is 0.375. The relationship between weather today and weather yesterday is following by table: Now,Peter has some recodes of the humidity of leaves in N days.And we know the weather conditons on the first day : the probability of sunny is 0.63,the probability of cloudy is 0.17,the probability of rainny is 0.2.Could you know the weathers of these days most probably like in order?
Input
The first line is T, means the number of cases, then the followings are T cases. for each case: The first line is a integer n(n<=50),means the number of days, and the next n lines, each line is a string shows the humidity of leaves (Dry, Dryish, Damp, Soggy)
Output
For each test case, print the case number on its own line. Then is the most possible weather sequence.( We guarantee that the data has a unique solution)
Sample Input
1 3 Dry Damp Soggy
Sample Output
Case #1: Sunny Cloudy Rainy
Hint
Log is useful.Author
FZU
Source
2014 Multi-University Training Contest 1
Recommend
We have carefully selected several similar problems for you: 4959 4958 4957 4956 4955
#include <algorithm>#include <cstring>#include <cstdio>#include <queue>#include <iostream>#include <vector>#include <string>#include <map>#include <cmath>#define REP(a,b,c) for(a=b;a<=c;a++)using namespace std;typedef long long ll;const ll inf= 1e8;const int N=52;const int M=16 ;double dp[N][5];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} };int n;int hash(string str){ if(str=="Dry")return 0; else if(str=="Dryish")return 1; else if(str=="Damp")return 2; else return 3;}int x[N],pa[N][3],ans[N];char * weather[3]={(char*)"Sunny",(char*)"Cloudy",(char*)"Rainy"};int run(){ string str; int _,cas=0; cin>>_; while(_--) { cin>>n; for(int i=1;i<=n;++i){ cin>>str; x[i] = hash(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 temp=dp[i-1][k]+log(p[k][j])+log(q[j][x[i]]); if(temp > dp[i][j] ) { dp[i][j]=temp; 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:\n",++cas); for(int i=1;i<=n;++i) printf("%s\n",weather[ans[i]]); } return 0;}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(0); return run();}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。