BZOJ1419:Red is good 期望dp

思路:

令\(f_{i,j}\)表示目前还剩\(i\)张红牌,\(j\)张黑牌时的期望最优利益.

有几种情况:

当\(i=0\)时,\(f_{i,j}=0\);

当\(j=0\)时,\(f_{i,j}=i\);

否则\(f_{i,j}=max(0,\frac{i}{i+j}(1+f_{i-1,j})+\frac{j}{i+j}(-1+f_{i,j-1}))\)

上面的概率枚举的是最上面一张牌的颜色.这应该很容易理解.

那么我们可以记忆化搜索,时间\(O(n^2)\),空间\(O(n^2)\).(MLE)

所以只能递推来做到\(O(n)\)的空间.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 5010
typedef double f2;
f2 f[2][N<<1];
 
f2 Max(f2 a,f2 b){if(a>b)return a;else return b;}
f2 solve(int n,int m){
    int now=0,lst=1;
    for(int i=1;i<=n+m;++i,now^=1,lst^=1){
        for(int j=0;j<=n&&j<=i;++j){
            if(!j)f[now][j]=0;else{if(j==i)f[now][j]=j;else f[now][j]=Max(0,(f[lst][j-1]+1)*j/i+(f[lst][j]-1)*(i-j)/i);}
        }
    }return f[lst][n];
}
int main(){
    int n,m;cin>>n>>m;
    f2 res=solve(n,m);
    long long count=(long long)(res*1000000);
    printf("%lld.%06lld",count/1000000,count%1000000);
    return 0;
}