@OceanEye7年前
05/3
18:56
期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)
|
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 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; int R,B; double dp[2][5050]; #define now i&1 #define pre now^1 int main() { read(R); read(B); for(int i=0;i<=B;i++) { for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j)))); } printf("%.6f",dp[B&1][R]-5e-7); return 0; } |