首页 > ACM题库 > HDU-杭电 > HDU 1437 天气情况-动态规划-[解题报告] C++
2013
12-10

HDU 1437 天气情况-动态规划-[解题报告] C++

天气情况

问题描述 :

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

输入:

我们这里假设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)。

输出:

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

样例输入:

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

样例输出:

0.400
0.300
0.250


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

睡不着,起床切了道水题.

HDU 1437



题意: 给你9个实数 Pij (1<=i,j<=3) 表示 1天后 从i天气变成j天气的概率.

再给M ,表示提问的次数。每次提问有3个数据,i,j,n,表示过了n天从i天气情况到j天气情况(1<=i,j<=3 1<=n<=1000)。



水题,设:dp[n][i] 为第n天为天气i的概率.



第n天天气可以有n-1天的天气算出

dp[n][i]=dp[n-1][1]*p[1][i]+dp[n-1][2]*p[2][i]+dp[n-1][3]*p[3][i]

程序如下:

#include"stdio.h"
#include"string.h"
double dp[1100][4];
double p[4][4];
int t,n;
int main()
{
  int a,b,c,i,m,k,j;
  scanf("%d",&t);
  while(t--)
  {
    for(i=1;i<=3;i++)
      for(j=1;j<=3;j++)
        scanf("%lf",&p[i][j]);
    scanf("%d",&m);
    for(k=1;k<=m;k++)
    {
      scanf("%d%d%d",&a,&b,&c);
      dp[0][1]=dp[0][2]=dp[0][3]=0.0;
      dp[0][a]=1.0;
      for(i=1;i<=c;i++)
      {
        dp[i][1]=dp[i-1][1]*p[1][1]+dp[i-1][2]*p[2][1]+dp[i-1][3]*p[3][1];
        dp[i][2]=dp[i-1][1]*p[1][2]+dp[i-1][2]*p[2][2]+dp[i-1][3]*p[3][2];
        dp[i][3]=dp[i-1][1]*p[1][3]+dp[i-1][2]*p[2][3]+dp[i-1][3]*p[3][3];
      }
      printf("%.3lf\n",dp[c][b]);
    }
  }
  return 0;
}

解题报告转自:http://blog.csdn.net/pygzx/article/details/7385603


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。