JS's Blog
0%

Poj 3744-Scout YYF I (概率dp+矩阵优化)

Posted on Edited on In ,

题目链接：
http://poj.org/problem?id=3744

题目大意：
一个人，一开始处于位置1，在n个位置上有地雷，不能接触，每次人有pp概率向前走一步，有1−p1-p概率向前跳两步，请问安全走过雷区的概率是多少,地雷位置x∈[1,100000000]x\in[1, 100000000]

分析：
dp[i]表示走到i处的概率的话，可以很快推出

dp[i]=p∗dp[i−1]+(1−p)∗dp[i−2]dp[i] = p*dp[i-1] + (1-p)*dp[i-2]

即dp[i]dp[i]是由dp[i−1]dp[i-1] 与dp[i−2]dp[i-2]贡献得到，那么从1开始，向上不断贡献，遇到地雷位置跳过，然后走到a[n]+1a[n]+1位置的概率即是答案，但是根据题意a[n]+1a[n]+1过大，且有多组数据，所有需要优化。

可以发现在每段中，情况几乎都相同，而且dp转移式很自然的能想到斐波那契F[i]=F[i−1]+F[i−2]F[i] = F[i-1] + F[i-2] ，所以这题可以用矩阵快速幂计算每一段的概率值，下一段的起点即是之前一个地雷的下一个位置，分别计算不走到各地雷的概率并作积即可

注意：

  • 地雷位置可以为1，即起点
  • 地雷读入为乱序
  • 地雷可能有重合
  • 地雷之间可能连续，即出现2，3连续位置的地雷

代码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;

const int maxn = 207;
const int mod = 1000000007;
const int Mod = 1000;
struct mat{
    int r,c;
    double m[10][10];
    mat(){}
    mat(int _r,int _c):r(_r),c(_c){};
};


void init(mat &a){
    memset(a.m,0,sizeof(a.m));
}

mat mul(mat a, mat b){
    mat tmp(a.r,b.c);

    for (int i = 1 ; i <= tmp.r; i ++)
    {
        for (int j = 1 ; j <= tmp.c ;j ++){
            tmp.m[i][j] = 0;
            for (int k =1 ; k <= a.c ; k ++){
                tmp.m[i][j] = (tmp.m[i][j]+(a.m[i][k]*b.m[k][j]));
            }
        }
    }
    return tmp;
}


mat QP(mat a ,int n){
    mat ans(a.r,a.r),tmp(a.r,a.r);
    memcpy(tmp.m,a.m,sizeof(tmp.m));
    init(ans);
    for (int i = 1 ; i <= ans.r ; i ++)
    {
        ans.m[i][i] = 1;
    }
    while (n){
        if (n&1)    ans = mul(ans,tmp);
        n >>= 1;
        tmp = mul(tmp,tmp);
    }
    return ans;
}


void print(mat a){
    for (int i = 1 ; i <= a.r ;++ i){
        for (int j = 1 ; j <= a.c ; ++j){
            printf("%f",a.m[i][j]);
            if (j==a.c) putchar('\n');
            else  putchar(' ');
        }
    }
}

int n;
double p;
int arr[maxn];
double dp[100000009];

int main()
{
    while (~scanf("%d%lf",&n,&p))
    {
        mat a(2,2);
        a.m[1][1] = p;
        a.m[1][2] = 1;
        a.m[2][1] = 1-p;
        a.m[2][2] = 0;
        for (int i =1 ; i <= n ; i ++)
            scanf("%d",&arr[i]);
        sort(arr+1,arr+n+1);
        if (arr[1] == 1)
            printf("%.7f\n",0);
        else
        {
            double t = 1;
            mat ans = QP(a,arr[1]-1);
            t *= (1-ans.m[1][1]);
            int f = 1;
            for (int i = 2 ; i <= n ; i ++)
            {

                if (arr[i]==arr[i-1])
                    continue;
                if (arr[i]-arr[i-1]==1)
                {
                    f = 0;
                    printf("%.7f\n",0);
                    break;
                }
                ans = QP(a,arr[i]-arr[i-1]-1);
                t *= (1-ans.m[1][1]);
            }
            if (f)
                printf("%.7f\n",t);
        }

    }
    return 0;
}