hdu 1437 天气情况【概率DP】

天气情况

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 638    Accepted Submission(s): 257

Problem Description

如果我们把天气分为雨天,阴天和晴天3种,在给定各种天气之间转换的概率,例如雨天转换成雨天,阴天和晴天的概率分别为0.4,0.3,0.3.那么在雨天后的第二天出现雨天,阴天和晴天的概率分别为0.4,0.3,0.3.现在给你今天的天气情况,问你n天后的某种天气出现的概率.

Input

我们这里假设1,2,3分别代表3种天气情况,Pij表示从i天气转换到j天气的概率.
首先是一个数字T表示数据的组数.
每组数据以9个数开始分别是P11,P12,P13,……,P32,P33,接着下一行是一个数字m,表示提问的次数。每次提问有3个数据,i,j,n,表示过了n天从i天气情况到j天气情况(1<=i,j<=3 1<=n<=1000)。

Output

根据每次提问输出相应的概率(保留3位小数)。

Sample Input

1

0.4 0.3 0.3 0.2 0.5 0.3 0.1 0.3 0.6

3

1 1 1

2 3 1

1 1 2

Sample Output

0.400

0.300

0.250

Hint:如果GC提交不成功,可以换VC试试

Author

xhd

题解:对于每一种情况都用前一天的所有情况的概率来分别乘以今天的单个情况的概率,如求第一天到第三天雨转到雨的概率,就需要用前一天(第二天)的所有情况,(雨,晴,阴)的概率来分别乘以今天的变雨的概率  同理,第二天的由第一天的推得

vis[j][k][i]+=map[l][k]*vis[j][l][i-1];

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 1100
#include<math.h>
#define DD double
DD map[4][4];
DD vis[4][4][MAX];
using namespace std;
int main()
{
	int n,m,j,i,t,k,l;
	int a,b,c;
	scanf("%d",&t);
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		for(i=1;i<=3;i++)
		    for(j=1;j<=3;j++)
		    {
		    	scanf("%lf",&map[i][j]);
		    	vis[i][j][1]=map[i][j];
		    }
		for(i=2;i<1010;i++)//天数
		{
			for(j=1;j<=3;j++)//由i天气
			{
				for(k=1;k<=3;k++)//转到k天气
				{
					for(l=1;l<=3;l++)//此循环用来循环天气的变化
					{
						vis[j][k][i]+=map[l][k]*vis[j][l][i-1];
						//第i天的j变k的概率   //map当前天每种天气转到k的概率
						// vis[j][l][i-1]前一天每种天气的概率
					}
				}
			}
		}
		scanf("%d",&n);
		while(n--)
		{
			scanf("%d%d%d",&a,&b,&c);
			printf("%.3lf\n",vis[a][b][c]);
		}
	}
	return 0;
}

  

时间: 11-25

hdu 1437 天气情况【概率DP】的相关文章

HDU 3366 Passage (概率DP)

Passage Problem Description Bill is a millionaire. But unfortunately he was trapped in a castle. There are only n passages to go out. For any passage i (1<=i<=n), Pi (0<=Pi<=1) denotes the probability that Bill will escape from this castle saf

HDU 4652 Dice (概率DP)

Dice Problem Description You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form: 0

[ACM] HDU 4576 Robot (概率DP,滚动数组)

Robot Problem Description Michael has a telecontrol robot. One day he put the robot on a loop with n cells. The cells are numbered from 1 to n clockwise. At first the robot is in cell 1. Then Michael uses a remote control to send m commands to the ro

[ACM] hdu 4405 Aeroplane chess (概率DP)

Aeroplane chess Problem Description Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the number

HDU 4050 wolf5x (概率DP 求期望)

题意:有N个格子,1~N,起点在0,每个格子有一个状态(0,1,2,3),每次可以跨[a,b]步, 问走完N个格子需要步数的期望,每次尽量走小的步数,即尽量走a步,不能则走a+1,-- 状态0意味着你不能踏进对应的网格. 状态1意味着你可以??步入网格用你的左腿. 状态2意味着你可以??步入网格用你的右腿. 状态3意味着你可以进入网格用任何你的腿,而接下来的步骤中,您可以使用任何的腿;即你不需要遵循上述规则. 思路:借鉴了各路大神的思想理解了下. dp[i][j] :表示走到第 i 个格子在 j

[ACM] hdu 3853 LOOPS (概率DP,递推)

LOOPS Problem Description Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl). Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth called LOOPS. The planform of the

HDU 4336 Card Collector(概率DP)

 题意:有n种卡片,吃零食的时候会吃到一些卡片,告诉你在一袋零食中吃到每种卡片的概率,求搜集齐每种卡片所需要买零食的袋数的期望. 思路:先状态压缩,然后概率DP 用d[i]表示由状态i到目标需要再买多少包,则状态转移方程为d[i] = p'*(d[i]+1) + sigma(d[ i | (1 << j) * p[i] ),然后相同项移到左边,最后就可以得到答案. #include<cstdio> #include<cstring> #include<cmat

HDU - 5001 Walk(概率dp+记忆化搜索)

Walk I used to think I could be anything, but now I know that I couldn't do anything. So I started traveling. The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an ad

hdu 4405 Aeroplane chess(概率DP 求期望__附求期望讲解方法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4405 Problem Description Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal p