[原创]LIGHTOJ 1265 - Island of Survival [递推|概率dp]【杂类|动态规划】

2017-01-12 15:48:15 Tabris_ 阅读数：326

博客爬取于2020-06-14 22:42:14
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54378682

题目连接：http://lightoj.com/volume_showproblem.php?problem=1265
--------------------------------------------------------------------------------.
1265 - Island of Survival
PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB
You are in a reality show, and the show is way too real that they threw into an island. Only two kinds of animals are in the island, the tigers and the deer. Though unfortunate but the truth is that, each day exactly two animals meet each other. So, the outcomes are one of the following

a) If you and a tiger meet, the tiger will surely kill you.
b) If a tiger and a deer meet, the tiger will eat the deer.
c) If two deer meet, nothing happens.
d) If you meet a deer, you may or may not kill the deer (depends on you).
e) If two tigers meet, they will fight each other till death. So, both will be killed.

If in some day you are sure that you will not be killed, you leave the island immediately and thus win the reality show. And you can assume that two animals in each day are chosen uniformly at random from the set of living creatures in the island (including you).

Now you want to find the expected probability of you winning the game. Since in outcome (d), you can make your own decision, you want to maximize the probability.

Input
Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing two integers t (0 ≤ t ≤ 1000) and d (0 ≤ d ≤ 1000) where t denotes the number of tigers and d denotes the number of deer.

Output
For each case, print the case number and the expected probability. Errors less than 10-6 will be ignored.

Sample Input

4
0 0
1 7
2 0
0 10

Output for Sample Input

Case 1: 1
Case 2: 0
Case 3: 0.3333333333
Case 4: 1

--------------------------------------------------------------------------------.
题目大意：
就是一座岛上有1个人t个老虎d只鹿，
现在每天都会有两只动物相遇，
老虎和人， 老虎会吃了人。
老虎和鹿，老虎会吃了鹿。
老虎和老虎，两只老虎都会死。
鹿和人，人可以吃鹿也可以不吃鹿。
鹿和鹿，什么也不会发生。

现在问你，最后人能活下来的概率。

解题思路：
首先还是分析一下，我们可以得到
1.鹿的存在对人能不能活下来是没有影响的。——所以考虑d的值没有任何意义
2.只有老虎全部死亡，人才能活下来。——又因为老虎只能两两自相残杀，所以只有t为偶数的时候人才有活下来的概率。

这时候问题其实可以转化为求在人与老虎相遇之前、偶数只老虎自相残杀全部死亡的概率，除此之外的其他相遇组合对结果无影响。

所以只要求每天人活下来的概率，累乘直到老虎全死了为止。

对于每一天人活下来的概率 = (两只老虎相遇的情况数)/(人和老虎总共可能相遇的情况数);即
t∗(t−1)2t∗(t+1)2\frac{\frac{t*(t-1)}{2} }{\frac{t*(t+1)}{2} }
约分一下
(t−1)(t+1)\frac{(t-1)}{(t+1)}
因为我们结果事t为2为止 所以总式子就是
(t−1)(t+1)∗((t−2)−1)((t−2)+1)∗...∗(2−1)(2+1)\frac{(t-1)}{(t+1)}*\frac{((t-2)-1)}{((t-2)+1)}*...*\frac{(2-1)}{(2+1)}
通过约分最后剩下的式子就变成了
1t+1\frac{1}{t+1}

这题就做完了

==================分割线==================
之后看了下题解，居然给的概率dp！
作为DP废还是学习下，
首先确定的是dp[t][d]就是t只老虎d只鹿的概率.
首先dp[0][0]=1;
算了 直接上菊苣的方法吧

1
2
3
4
5
6
7
8
9
10
设dp[t][d]表示还有t只老虎，d只鹿的时候，存活的概率。
那么就有dp[0][0]=1
根据概率dp的方程当前状态=Σ(转移到某个状态的概率*那个概率存活的概率)
那么我们只要按题意去转移就好了。
对于人与鹿吃还是不吃的情况，我们直接算出两种转移方式的存活概率，然后取最大值就可以了。
对于两头鹿的情况，可以发现这种情况最后会从自己本身转移，我们通过移项，把右边的项移到左边去，那么就可以使得左边的系数减小。对于这种情况我们只需要维护一下左边的系数，最后再把答案除以左边的系数就可以了。
那么dp[t][d]就是最后的答案

菊苣的概率DP的代码
http://paste.ubuntu.net/23738804/

附本题代码
-------------------------------.

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
# include <bits/stdc++.h>
using namespace std;
# define abs(x) ((x>=0)?(x):-(x))
typedef long long int LL;
const int MOD = 1e9;
const int N = 1000+7;
/*******************************************/
double dp[N][N];

int main(){

    int _,kcase = 0,t,d;
    scanf("%d",&_);
    while(_--){
        scanf("%d %d",&t,&d);
        printf("Case %d: ",++kcase);
        if(0==t) puts("1");
        else if(t%2==1) printf("0\n");
        else {
            double ans = (double)(1+t);
            printf("%.9lf\n",1.0/ans);
        }
    }
    return 0;
}