poj 3744 Scout YYF I（矩阵优化概率） - c++编程基础

TOP

poj 3744 Scout YYF I（矩阵优化概率）

2015-07-20 17:45:22 来源: 作者: 【大中小】浏览:2次

有n个雷，某人的起始位置在1，每次走一步的概率为p,走两步的概率是1-p,给出n个雷的位置，问最后成功走出雷区的概率。

放在高中应该是很简单的分步乘法求概率。即把每一个雷都没踩到的概率求出来，最后n个相乘就是顺利通过的概率。对于输入的n个位置进行分段1~num[1],num[1]+1~num[2]......每一段都只有一个雷num[i]，每一段内踩不到雷的概率就是1-踩到num[i]雷的概率。

设dp[i]表示踩到第i个雷的概率，那么dp[i] = p*dp[i-1] + (1-p)*dp[i-2]，因为i较大，可以用矩阵相乘进行优化。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL __int64 #define LL long long #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; struct matrix { double mat[2][2]; void init() { mat[0][0] = mat[1][1] = 1; mat[0][1] = mat[1][0] = 0; } }a,b,res; int num[15]; int n; double p; matrix mul(matrix x, matrix y) { matrix t; memset(t.mat,0,sizeof(t.mat)); for(int i = 0; i < 2; i++) { for(int k = 0; k < 2; k++) { if(x.mat[i][k] == 0) continue; for(int j = 0; j < 2; j++) { t.mat[i][j] += x.mat[i][k]*y.mat[k][j]; } } } return t; } matrix pow(matrix a, int n) { matrix t; t.init(); while(n) { if(n&1) t = mul(t,a); n >>= 1; a = mul(a,a); } return t; } int main() { while(~scanf(%d %lf,&n,&p)) { a.mat[0][0] = p; a.mat[0][1] = 1-p; a.mat[1][0] = 1; a.mat[1][1] = 0; memset(b.mat,0,sizeof(b.mat)); b.mat[0][0] = 1; b.mat[1][0] = 0; for(int i = 1; i <= n; i++) scanf(%d,&num[i]); sort(num+1,num+1+n); double ans; res = pow(a,num[1]-1); res = mul(res,b); ans = 1 - res.mat[0][0]; for(int i = 2; i <= n; i++) { res = pow(a,num[i]-num[i-1]-1); res = mul(res,b); ans *= (1-res.mat[0][0]); } printf(%.7f ,ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Android - JNI添加标准C++文件	下一篇：uva 1358 - Generator(KMP+期望)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: