LightOJ - 1265 Island of Survival 腦洞 機率DP 1月3日

【題目連結】​​點選打開連結​​

【題意】 島上有一個人,t隻老虎和d隻鹿,每天都會有兩個生物随機碰面,有以下幾種情況①老虎與人碰面,人被吃掉②老虎與鹿碰面,鹿被吃掉③老虎與老虎,兩隻老虎同歸于盡④鹿與鹿碰面,什麼都不會發生⑤鹿與人碰面,人可以選擇殺死鹿或不殺鹿(取決于你),問最後人存貨下來的最大機率.

【解題方法1】經典的機率DP問題,設a[i][j]為島上剩i隻老虎和j隻鹿的情況,計算每個a[i][j]時先算出第①②③種情況,随後再按照機率算出後兩種情況的做法會比較好處理,因為會涉及某一狀态有某種機率會指向自己的情況.

double dp[maxn][maxn];
void init()
{
    dp[0][0] = 1;
    for(int t = 0; t < maxn; t++){
        for(int d = 0; d < maxn; d++){
            if(!t && !d) continue;
            double xi = 1, ans = 0, tdp;
            if(d >= 1 && t >= 1) dp[t][d] += 2.0 * t / (t + d + 1) * d / (t + d) * dp[t][d - 1];
            if(d >= 2) xi -= 1.0 * d / (t + d + 1) * (d - 1) / (t + d);
            if(t >= 2) dp[t][d] += 1.0 * t / (t + d + 1) * (t - 1) / (t + d) * dp[t - 2][d];
            ans = dp[t][d] / xi;
            if(d > 0){
                tdp = dp[t][d] + 2.0 / (t + d + 1) * d / (t + d) * dp[t][d - 1];
                tdp /= xi;
                ans = max(ans, tdp);
            }
            dp[t][d] = ans;
        }
    }
}

int main()
{
    int T, ks = 0;
    init();
    scanf("%d", &T);
    while(T--)
    {
        int t, d;
        scanf("%d%d", &t, &d);
        printf("Case %d: %.10f\n", ++ks, dp[t][d]);
    }
    return 0;
}      

【解題方法2】 方法2來自BLOG:

​​點選打開連結​​

因為在整個決策過程中,鹿的存在與否并不會對最後的結果産生影響,why?Becase決定人最後存活與否的最關鍵的因素在于老虎們是否全部死亡,而鹿并不會讓人或者老虎數量發生變化,且讓老虎死亡的唯一可能就是在某天有兩隻老虎碰面了,而且老虎如果死亡則一定是成雙成對地死(<_<),是以我們計算人最後存活的機率則等價于計算老虎在碰見人之前就全部gg的機率.

是以結論就很明顯了,當老虎是奇數時,人一定會死,當老虎數量為0時,則人一定存活,而當老虎的數量為非零偶數時,設有t隻老虎,無視掉鹿參與碰面的情況,則在前t/2個有老虎參與碰面的日子裡(因為有t隻老虎,是以第t/2+1天時隻會剩下一隻虎或一個人)選取t個生物參與碰面,若不區分老虎,則總情況數為C(t+1,t)=C(t+1,1)=t+1,而人能存活的情況就是選取的t個生物為全部的t隻老虎,情況數為C(t,t)=1,則人最後能夠存活的機率便是(能夠存活的情況)/(總情況)=1/(t+1),這道題到這兒才算是完美解出.

int main()
{
    int T, ks = 0;
    scanf("%d", &T);
    while(T--)
    {
        int t, d;
        scanf("%d%d", &t, &d);
        if(t == 0) printf("Case %d: 1.000000000\n", ++ks);
        else if(t % 2 == 1) printf("Case %d: 0.000000000\n", ++ks);
        else printf("Case %d: %.10f\n", ++ks, 1.0 / (t + 1));
    }
    return 0;
}