POJ 3744 Scout YYF I

题意

某人在直线上走,直线上有若干格子,起点是1号格,每次这个人都有p概率走1格,1-p概率走二格,有一些格子有地雷,走上去就被爆了,所以要你求你能安全走到终点(可以看成是站在n+1号格)上概率。

思路

每一个格子的概率都可以通过它前两个的格子的概率推出来,这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么?快速幂。
所以这个题我们用快速幂来做。

dp方程其实都不叫dp,叫递推,大概长这个样子:

\begin{bmatrix}p&1-p\\1&0 \end{bmatrix}\begin{bmatrix}p_{n} \\ p_{n-1}\end{bmatrix}=\begin{bmatrix} p_{n+1}\\p_{n}\end{bmatrix}

直接矩阵乘法模版+快速幂就行。

处理地雷的话,你就先走到地雷那里,停一下,把地雷格的dp值抹成0,然后继续往下走,走到下一个地雷,最后走到终点。

代码

 

1 Comment

  1. wingkou
    January 26, 2016

    #include
    #include
    #include
    using namespace std;
    int main()
    {
    int n, mine[16];
    double p;
    while (scanf(“%d%lf”, &n, &p) == 2)
    {
    for (int i = 0; i < n; i++)
    scanf("%d", mine + i);
    sort(mine, mine + n);
    int cur = 1;
    double curp = 1;
    for (int i = 0; i < n; i++)
    {
    curp *= 1 – ((1 – p) * pow(p – 1, mine[i] – cur) + 1) / (2 – p);
    cur = mine[i] + 1;
    }
    printf("%.7fn", curp);
    }
    return 0;
    }

    Reply

Leave a Reply

Scroll to top