又是一道坑题HDU4405

发表于 | 分类于

最近打算刷几道概率DP，然而就这么状况频出。。。

丢个链接：

HDU4405

这道题的大意是说Hzz玩儿飞行棋，起点是0，终点是n，并且路径上还有m条航线(x,y)可以不用掷骰子直接从x到y。问掷骰子次数的期望。

明明是一道裸题，结果又WA了好几遍。看讨论才发现若x点存在航线的话直接飞，不考虑掷骰子的事儿。然而原文中说的是

The i-th flight line can help Hzz fly from grid Xi to Yi (0<Xi<Yi<=N) without throwing the dice.

我也不知道这个“help”咋就成强制的了，因为可能会存在这种情况：

1
2
3
4
5
6
7
8
9
12 7
1 8
2 12
3 12
4 12
5 12
6 12
7 12
0 0

这样的数据，当第一次掷出1时很明显不选走航线是更优的。。。不是很明白飞行棋的规矩，但是按照题目里的说明应该是可以选择飞不飞吧。。。然而这么打就错了，强制飞就对了。。。辣鸡HDU。。。

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
33
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
double f[100005];
int to[100005];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n)
    {
        memset(f,0,sizeof(f));
        memset(to,0,sizeof(to));
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            to[a]=b;
        }
        for(int i=n-1;i>=0;i--)
        {
            for(int j=1;j<=6;j++)
            {
                f[i]+=f[i+j];
                if(i+j==n)break; 
            }
            f[i]=f[i]/6.0+1;
            if(to[i])f[i]=min(f[i],f[to[i]]);
        }
        printf("%.4lf\n",f[0]);
    }
    return 0;
}