杰 & C++ & Python & DM

POJ Scout YYF I 解题报告

/*
*   Pro(i)表示不遇到雷的情况下，到达i步的几率，那么
*       Pro(n) = Pro(n-1) * p + Pro(n-2) * (1-p)
*   首先求递推公式，由特征方程 x^2 - p*x -(1-p) = 0 求得特征根: p-1 和 1
*   所以Pro(n) = C1 + C2*(p-1)^n
*   将Pro(1)=1 Pro(2)=p代入，求得待定系数C1 = -1/(p-2), C2 = 1/(p-2)
*   故Pro(n) = -1/(p-2) + 1/(p-2)^n
*
*   假设在位置k首次遇到雷，那么到达位置k-1的几率是 Pro(k-1)
*   经过雷后存活的几率是 Pro(k-1) * (1-p)
*   将这个值即为a
*   
*   假设又经过t步第二次遇到雷，那么到达t-1步的几率是 a*Pro(t-1)
*   经过雷后存活的几率是 a * Pro(t-1) * (1-p)
*
*   以此类推
*/

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    const int SIZE = 15;
    int iMineNum;
    double p;
    int pMinePos[SIZE];     //记录雷的位置 
    double pRes[SIZE];      //pRes[i]表示经过雷i后存活下来的几率 
    
    while(scanf("%d%lf",&iMineNum,&p) != EOF)
    {
        *(pMinePos+0) = 0;              //  为了统一后面的计算 
        for(int i=1; i<=iMineNum; ++i)
            scanf("%d", (pMinePos+i));    
                    
        sort(pMinePos,pMinePos + iMineNum + 1);     //对雷的位置进行排序 
           
        pRes[0] = 1;                    //  为了统一后面的计算  
        
        for(int i=1; i<=iMineNum; ++i)
        {
            /**//*计算遇到雷之前，存活的几率*/ 
            pRes[i] =  -1/(p-2) + 1/(p-2) * pow((p-1),pMinePos[i]-pMinePos[i-1]-1);
            
            /**//**/
            pRes[i] *= (1-p) * pRes[i-1];
        }       
        printf("%.7lf\n",pRes[iMineNum]);        
    }    
    return 0;    
}

posted on 2009-09-12 21:36 jaysoon 阅读(160) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC