codeforces.148D(概率dp,360笔试题)

Bag of mice

A,B两人轮流抽取卡片，有n张中奖的，m张无奖的，A,B抽取完后卡片丢弃，
但是B还可以在抽取一张丢弃(即使是中奖的也丢弃)，一方取到中奖游戏结束。

A,B的情况倒推过去就行。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
double dp[2][1003][1003];
double ans=0;
int main(){
    int n,m;
    cin>>n>>m;
    if(n==0)return O(0);
    if(m==0)return O(1);
    dp[0][n][m]=1;
    for(int i=n;i>=1;i--){
        for(int j=m;j>=0;j--){
            if(j-2>=0){
                dp[0][i][j-2]+=dp[1][i][j]*(1.0*j/(i+j))*(1.0*(j-1)/(i+j-1));
            }
            if(i-1>0&&j-1>=0){
                dp[0][i-1][j-1]+=dp[1][i][j]*(1.0*j/(i+j))*(1.0*i/(i+j-1));
            }
            if(j-1>=0)dp[1][i][j-1]+=dp[0][i][j]*(1.0*j/(i+j));
            ans+=dp[0][i][j]*(1.0*i/(i+j));
        }
    }
    pr("%.10f\n",ans);
}