HDU3853 LOOPS

发表于 | 分类于

先丢个题目链接。
题目大意是此主人公（马猴烧酒，话说前几天才和yzyun大佬谈论过这个梗= =）处在一个r*c的矩阵的左上角 ，她需要去到右下角，在每个点上，她有grid(r,c)的概率留在原地，有grid(r,c+1)的概率向右走，有grid(r+1,c)的1概率向下走，每次走动都需要花费2点能量值。求到终点的期望能量值花费。

一道很裸的期望DP，倒推期望，设f[i][j]为从点(i,j)到终点的期望，可推得，当s[i][j]不为1时，f[i][j]=(f[i+1][j]*d[i][j]+f[i][j+1]*rm[i][j]+2)/(1-s[i][j])，否则f[i][j]直接为0。一些变量的意义请直接见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
double d[1003][1003],rm[1003][1003];//d代表向下的概率，rm代表向右的概率
double s[1003][1003],f[1003][1003];//s代表留在原地的概率，f代表期望花费
int main()
{
    int r,c;
    while(scanf("%d%d",&r,&c)!=EOF)
    {
        memset(f,0,sizeof(f));
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                scanf("%lf%lf%lf",&s[i][j],&rm[i][j],&d[i][j]);
            }
        }
        for(int i=r;i>=1;i--)
        {
            for(int j=c;j>=1;j--)
            {
                if(i==r&&j==c)continue;
                if(s[i][j]==1)continue;
                f[i][j]=(f[i+1][j]*d[i][j]+f[i][j+1]*rm[i][j]+2)/(1-s[i][j]);
            }
        }
        printf("%.3lf\n",f[1][1]);
    }
    return 0;
}

按理说这道题挺简单的，然而却有几个不大不小的槽点。这道题我第一遍交的时候按照每个点一组数据，数组开的float，结果WA了，第二遍开的double，按每个点多数据打的，然后就A了。。。不知道是精度问题还是hdu又一次不带提醒的用的多数据。。。。还有一个槽点的是答案保证不超过1000000，然而若中间的某点只能在原地走的话，期望就是INF，而我们把这样的点的期望赋值成了0，就相当于把这个点当成了又一个终点，可能会导致答案错误，不清楚数据是不是特意避开了这样的情况，还是标程就是错的没有考虑这种情况，反正我A了~如果有哪位dalao知道赋值为INF的正确做法的话，欢迎指出发到我邮箱里sounkix@outlook.com，非常感谢！