JZTXT

Codeforces Round 105 (Div. 2) - D. Bag of mice DP 或 记忆化搜索 求概率

发布时间 2023-07-29 22:25:32作者: Qiansui

D. Bag of mice

题意

待补充~

思路

可利用 DP 或者记忆化搜索求解本问题，实际上这两个方法等价。

代码

  • 记忆化搜索
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
上一发DP，这一发记忆化搜索
*/
const int maxm = 1e3 + 5, inf = 0x3f3f3f3f, mod = 998244353;
double dp[maxm][maxm];

double dfs(int n, int m){
	if(n <= 0 || m < 0) return 0;       //attention!
	if(m == 0) return 1;
	if(dp[n][m] != 0) return dp[n][m];
	dp[n][m] = 1.0 * n / (n + m);
	if(n + m >= 3){
		dp[n][m] += dfs(n - 1, m - 2) * m * (m - 1) * n / (n + m) / (n + m - 1) / (n + m - 2)
			+   dfs(n, m - 3) * m * (m - 1) * (m - 2) / (n + m) / (n + m - 1) / (n + m - 2);
	}
	return dp[n][m];
}

void solve(){
	int n, m;
	cin >> n >> m;
	cout << fixed << setprecision(9) << dfs(n, m) << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}
  • DP
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 1e3 + 5, inf = 0x3f3f3f3f, mod = 998244353;
double dp[maxm][maxm];

void solve(){
	for(int i = 0; i < maxm; ++ i){
		dp[i][0] = 1;
		dp[0][i] = 0;
	}
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j <= m; ++ j){
			dp[i][j] = 1.0 * i / (i + j);
			if(i + j >= 3){
				if(j >= 2)
					dp[i][j] += dp[i - 1][j - 2] * j * (j - 1) * i / (i + j) / (i + j - 1) / (i + j - 2);
				if(j >= 3)
					dp[i][j] += dp[i][j - 3] * j * (j - 1) * (j - 2) / (i + j) / (i + j - 1) / (i + j - 2);
			}
		}
	}
	cout << fixed << setprecision(9) << dp[n][m] << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}