lightoj1265 Island of Survival(思维或dp)

vj传送门

$首先说一下非概率dp的解法$

说实话我看到就觉得自己傻X了

鹿这个物种是没啥用的,既不会影响老虎的数量也不会影响人的数量

而我们最后是否存活只和是否有老虎相关

所以有多少鹿是无所谓的!!只有老虎和老虎的相遇有意义!!

所以相当于$t$只老虎和$1$个人

当$t$为奇数概率为零,否则是$\frac{1}{t+1}$的概率赢

就是就是$\frac{t}{t+1}\ast \frac{t-1}{t}\ast \frac{t-2}{t-1}...\ast \frac{1}{2}$,然后只剩下一个人

$然后是概率dp$

设老虎$i$只,鹿$j$只,令$s=i+j$

$Ⅰ.老虎和人相遇的概率是p_1=\frac{2i}{s\ast (s+1)}$

$Ⅱ.老虎和鹿p_2=\frac{2ij}{s\ast (s+1)}$

$Ⅲ.鹿和鹿p_3=\frac{j\ast (j-1)}{s\ast (s+1)}$

$Ⅳ.人和鹿p_4=\frac{2j}{s\ast (s+1)}$

$Ⅴ.老虎和老虎p_5=\frac{i\ast (i-1)}{s\ast (s+1)}$

假如当人碰到鹿,选择宰掉鹿

$$f[i][j]=p_2\ast f[i][j-1]+p_3\ast f[i][j]+p_4\ast f[i][j-1]+p_5\ast f[i-2][j]$$

$$(1-p_3)\ast f[i][j]=p_2\ast f[i][j-1]+p_4\ast f[i][j-1]+p_5\ast f[i-2][j]$$

假如当人碰到鹿,选择放鹿一马

$$f[i][j]=p_2\ast f[i][j-1]+p_3\ast f[i][j]+p_4\ast f[i][j]+p_5\ast f[i-2][j]$$

$$(1-p_3-p_4)\ast f[i][j]=p_2\ast f[i][j-1]+p_5\ast f[i-2][j]$$

二者取$max$即可,无脑概率$dp$

#include <bits/stdc++.h>
using namespace std;
double f[1009][1009];
int main()
{
	int T,n,m,casenum=0; cin >> T;
	while( T-- )
	{
		cin >> n >> m;//老虎和麋鹿 
		for(int i=0;i<=m;i++)	f[0][i]=1.0;
		for(int i=1;i<=n;i++)//枚举老虎的量
		for(int j=0;j<=m;j++)
		{
			if( i%2==1 )	f[i][j]=0.0;
			else
			{
				double s=(i+j)*(i+j+1);
				double p1 = 2.0*i/s;//和老虎相遇 
				double p2 = 2.0*i*j/s;
				double p3 = j*(j-1.0)/s;
				double p4 = 2.0*j/s;
				double p5 = i*(i-1.0)/s;
				double killer=0,goodman=0;
				if( j>=1 )	killer+=(p2+p4)*f[i][j-1];
				killer = ( killer+p5*f[i-2][j] )/(1-p3);
				if( j>=1 )	goodman+=p2*f[i][j-1];
				goodman = ( goodman+p5*f[i-2][j] )/(1-p3-p4);
				f[i][j] = max( killer,goodman );
			}
		}
		printf("Case %d: %.7lf\n",++casenum,f[n][m] );
		for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++) 	f[i][j]=0;
	}	
} 

本文地址：https://blog.csdn.net/jziwjxjd/article/details/109234690