杰 & 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 閱讀(175) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC