TopCoder SRM420 Div1 RedIsGood —

TopCoder SRM420 Div1 RedIsGood —— 期望

题目链接：https://vjudge.net/problem/TopCoder-9915
（论文上的题）
题解：
更正：， i>0, j>0
代码如下：
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cmath>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 const double EPS = 1e-6;
 15 const int INF = 2e9;
 16 const LL LNF = 9e18;
 17 const int MOD = 1e5;
 18 const int MAXN = 1e3+10;
 19 
 20 // 记忆化搜索
 21 double dp[MAXN][MAXN];
 22 bool vis[MAXN][MAXN];
 23 double dfs(int r, int b)
 24 {
 25     if(r==0) return 0;  //当没有红牌剩余时，停止翻牌，则期望为0
 26     if(b==0) return r;  //当没有黑牌剩余时，将剩余的红牌全部翻完，则期望为r
 27 /*  if(r<=b) return 0;
 28     本来认为如果红小于黑时，就停止翻牌，期望为0.但是当r<=b时，期望仍有可能大于0，
 29     因为允许在任意时刻停止翻牌，即在前景对自己不利的时候停止。
 30     比如1 1，EX = 0.5*1 + 0.5*(-1+1.0*1) = 0.5。 第一部分：当翻完红牌时，
 31     前景，即期望是对自己不利的，因而马上停止。
 32 */
 33     if(vis[r][b]) return dp[r][b];
 34     vis[r][b] = true;
 35     return dp[r][b] =  max(0.0, 1.0*r/(r+b)*(dfs(r-1,b)+1) + 1.0*b/(r+b)*(dfs(r,b-1)-1));
 36 }
 37 
 38 int main()
 39 {
 40     int R, B;
 41     while(scanf("%d%d", &R, &B)!=EOF)
 42     {
 43         memset(vis, false, sizeof(vis));
 44         printf("%.3lf
", dfs(R,B));
 45     }
 46 }
 47 
 48 /* 递推
 49 double dp[MAXN][MAXN];
 50 int main()
 51 {
 52     int R, B;
 53     while(scanf("%d%d", &R, &B)!=EOF)
 54     {
 55         for(int i = 0; i<=B; i++)   //当没有红牌剩余时，停止翻牌，即期望为0
 56             dp[0][i] = 0;
 57         for(int i = 1; i<=R; i++)
 58         {
 59             dp[i][0] = i;
 60             for(int j = 1; j<=B; j++)   //如果剩余的期望小于0，就不再翻牌了。
 61                 dp[i][j] = max(0.0, 1.0*i/(i+j)*(dp[i-1][j]+1) + 1.0*j/(i+j)*(dp[i][j-1]-1));
 62         }
 63         printf("%.3lf
", dfs(R,B));
 64     }
 65 }
 66 */
 67 
 68 /* 滚动数组
 69 double dp[MAXN];
 70 int main()
 71 {
 72     int R, B;
 73     while(scanf("%d%d", &R, &B)!=EOF)
 74     {
 75         for(int i = 0; i<=B; i++)
 76             dp[i] = 0;
 77         for(int i = 1; i<=R; i++)
 78         {
 79             dp[0] = i;
 80             for(int j = 1; j<=B; j++)
 81                 dp[j] = max(0.0, 1.0*i/(i+j)*(dp[j]+1) + 1.0*j/(i+j)*(dp[j-1]-1));
 82         }
 83         printf("%.3lf
", dp[B]);
 84     }
 85 }
 86 */
 87 
 88 /*
 89 int R, B;
 90 double dp[MAXN][MAXN]; //另一种dp[i][j]的定义：当前翻了i张红，j张黑，剩余的期望为多少。
 91 bool vis[MAXN][MAXN];
 92 double dfs(int r, int b)
 93 {
 94     if(r==R) return 0;
 95     if(b==B) return R-r;
 96     if(vis[r][b]) return dp[r][b];
 97     vis[r][b] = true;
 98     return dp[r][b] =  max(0.0, 1.0*(R-r)/(R+B-r-b)*(dfs(r+1,b)+1) + 1.0*(B-b)/(R+B-r-b)*(dfs(r,b+1)-1));
 99 }
100 
101 int main()
102 {
103     while(scanf("%d%d", &R, &B)!=EOF)
104     {
105         memset(vis, false, sizeof(vis));
106         printf("%.3lf
", dfs(0,0));
107     }
108 }
109 */
View Code