CF# 301 D Bad Luck Island（概率dp+记忆化）

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e⑻ typedef __int64 ll; #define fre(i,a,b) for(i = a; i <b; i++) #define free(i,b,a) for(i = b; i >= a;i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define ssf(n) scanf("%s", n) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi ") using namespace std; #define INF 0x3f3f3f3f #define N 105 int r,s,p; double dp[N][N][N]; double dfs(int pre,int now,int nest) //pre吃now，now吃nest，nest吃pre，最后pre存活的几率 { if(dp[pre][now][nest]>=0) return dp[pre][now][nest]; if(pre==0) return 0; if(nest==0) return pre ? 1:0; double ans=0; if(pre&&now) ans+=(pre*now*1.0)/(pre*now+now*nest+pre*nest)*dfs(pre,now⑴,nest); //pre吃now if(now&&nest) ans+=(now*nest*1.0)/(pre*now+now*nest+pre*nest)*dfs(pre,now,nest⑴); //now吃nest， if(pre&&nest) ans+=(pre*nest*1.0)/(pre*now+now*nest+pre*nest)*dfs(pre⑴,now,nest); //nest吃pre dp[pre][now][nest]=ans; return ans; } int main() { int i,j,n; mem(dp,⑴); while(~scanf("%d%d%d",&r,&s,&p)) { printf("%.10lf ",dfs(r,s,p)); printf("%.10lf ",dfs(s,p,r)); printf("%.10lf ",dfs(p,r,s)); } return 0; }