【LightOJ - 1265 Island of Survival 】概率期望DP

LightOJ - 1265 Island of Survival

题意

你现在进入一片森林，森林中有n只老虎m只鹿，森林中有几个法则。

• 如果两个老虎相遇，两个老虎都会死亡
• 如果一只老虎遇见一只鹿，鹿会被老虎吃掉
• 如果两只鹿相遇，什么也不会发生
• 如果你遇到一只老虎，你会被老虎吃掉
• 如果你遇到一只鹿，你可以选择杀掉这个鹿或者放走这个鹿

现在求你能活下来的概率。

做法

这道题有两个做法，但是不管哪种做法，首先要知道如果老虎的个数是奇数个，一定活不了。
概率DP：
我们设dp[i][j]表示草原上有i只老虎j只鹿能活下来的概率。
首先如果没有老虎，不管有多少只鹿都一定可以存活，之后转移即可。
dp[i][j]可以从以下几个状态转移过来

• dp[i-2][j]，表示两只老虎相遇，概率为$\frac{i?(i?1)}{(i+j+1)?(i+j)}$
• dp[i][j-1]，表示一只老虎一只鹿相遇，概率为$\frac{2?i?j}{(i+j+1)?(i+j)}$
• dp[i][j]，表示两只鹿相遇，概率为$\frac{j?(j?1)}{(i+j+1)?(i+j)}$

对于人遇见鹿的情况

• 如果选择杀掉鹿，则从dp[i][j-1]转移过来，概率为$\frac{2?j}{(i+j+1)?(i+j)}$
• 如果选择放走鹿，则从dp[i][j]转移过来，概率为$\frac{2?j}{(i+j+1)?(i+j)}$

转移时对两种转移取max即可。

第二种做法：

考虑到鹿在这道题中没有任何作用，老虎是否会吃掉鹿，和他之后吃掉人没有任何关系，所以我们可以考虑草原上只有老虎和人两种生物，如果人想存活需要老虎的个数是偶数而且一直自相残杀，所以我们只要求出两只老虎不断相遇的概率即可，如果当前老虎数为x，那么从老虎和人中随意选出两个的方案数为$x?(x+1)$,选出两只老虎的方案数为$x?(x?1)$,所以两只老虎相遇的概率为$\frac{x?1}{x+1}$，之后不段缩小问题规模求解即可。

代码

做法1

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e3+5;
double dp[maxn][maxn];
int main()
{
    int t;scanf("%d",&t);int cas=0;while(t--){
    int n,m;scanf("%d%d",&n,&m);if(n&1) printf("Case %d: 0\n",++cas);else{
    for(int i=0;i<=m;i++) dp[0][i]=1;for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
    double down = (i+j+1)*(i+j);double p1 = 1.0*(i*(i-1))/down;double p2 = 2.0*(i*j)/down;double p3 = 1.0*(j*(j-1))/down;double p4 = 2.0*j/down;down = 1-p3-p4;double res1=0;if(i-2>=0) res1=res1+dp[i-2][j]*p1/down;if(j>=1) res1=res1+dp[i][j-1]*p2/down;double res2=0;down= 1-p3;if(i-2>=0) res2=res2+dp[i-2][j]*p1/down;if(j>=1) res2=res2+dp[i][j-1]*p2/down;if(j>=1) res2=res2+dp[i][j-1]*p4/down;dp[i][j]=max(res1,res2);}}printf("Case %d: %.12f\n",++cas,dp[n][m]);}}return 0;
}

做法2

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int t;scanf("%d",&t);int cas=0;while(t--){
    int n,m;scanf("%d%d",&n,&m);if(n&1) printf("Case %d: 0\n",++cas);else{
    double ans=1.00;while(n){
    ans=ans*1.0*(n-1)/(n+1);n-=2;}printf("Case %d: %.12f\n",++cas,ans);}}return 0;
}