Acwing 623. 投票 【概率dp】

dp[i][j] ： 表示A被投了i票，B被投了j票，并以这个状态开始往后一直是i>j的概率
看数据范围N和M都是2000，那么就可以把所有范围的i和j表示出来

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 2e3+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------
int T;
int N,M;
double eps = 1e-9;
double dp[2020][2020];
double dfs(int i,int j){
    if(i == N || j == M) return 1;//比赛结束，这时候肯定是A赢了，所以概率是1
    if(dp[i][j] >= 0) return dp[i][j];
    int left = N + M - i - j;
    double ans = 0;
    if(i - j > 1){
        ans += (double)(N-i)/left * dfs(i+1,j);
        ans += (double)(M-j)/left * dfs(i,j+1);
    }else if(i-j == 1){
        ans +=  (double)(N-i)/left * dfs(i+1,j);
    }
    return dp[i][j] = ans;
}
int main() {
//    debug_in;
//    debug_out;

    read(T);
    go(Case,1,T){
        read(N,M);
        double ans;

        if(N<=M) ans = 0;
        else{
            go(i,0,N) go(j,0,M) dp[i][j] = -1.0;
            ans = (double)N/(N+M) * dfs(1,0);
        }
        printf("Case #%d: %.8f\n",Case,ans);
    }

    return 0;
}