把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF148D Bag of Mice
题目大意：有b只黑老鼠和w只白老鼠（都<=1000），公主先抽，公主抽完不会有任何变化，只是抽到的老鼠消失，龙抽完之后除了被抽的那只消失，还有另一只会跑出去，他们俩谁先抽到白老鼠谁赢，问公主赢的概率。

解：

概率DP入门题，求概率顺推，求期望逆推，本题的状态非常好想：dp[i][j]表示还剩下i只白老鼠和j只黑老鼠并轮到公主抽卡（？）的概率，那么这个概率乘上公主抽到白老鼠的概率就是答案的一部分，而如果没抽到的话，龙有两种情况，一种是抽到黑老鼠并有白老鼠跑了，一种是抽到黑老鼠并有黑老鼠跑了，两种都可以顺利转移，只要求一下概率就行。
概率DP定态的关键是找到一定操作后的“现状”，因为只有有了现状才能去推到下一步，本题实际上完全无法表现概率DP真正困难的地方，但是却有定态现状的思想，所以还算适合作为入门题去考虑。题目也没有什么坑，记得特判组合数越界的情况以及两个都为0的情况（因为C00等于1所以会出错）。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 500005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
double dp[1001][1001];
inline double C(int btm, int top) {
	if (btm == 0)return 0;
	if (top == 0)return 1;
	if (top == 1) {
		return (double)btm;
	}
	else {
		return (double)btm * (double)(btm - 1.0) / 2.0;
	}
}
int main() {
	//cfast;
	int w, b;
	cin >> w >> b;
	if (w + b == 0) {
		cout << "0.000000000";
		return 0;
	}
	double ans = 0;
	dp[w][b] = 1;
	for (int i = w; i >= 0; i--) {
		for (int j = b; j >= 0; j--) {
			if (dp[w][b] != 0){
				if (j != 0)
					ans += dp[i][j] * C(i, 1) / C(i + j, 1);
				else ans += dp[i][j];
			}
			if (i >= 1 && j >= 2) {
				double mul = C(j, 1) / C(j + i, 1) * C(j - 1, 1) / C(i + j - 1, 1) * C(i, 1) / C(i + j - 2, 1);
				dp[i - 1][j - 2] += dp[i][j] * mul;
	///			cout << "editing" << i - 1 << "." << j - 2 << "mul="<<mul<<endl;
			}
			if (j >= 3) {
				dp[i][j - 3] += dp[i][j] * C(j, 1) / C(j + i, 1) *C(j-1,2)/C(j+i-1,2);
			}
		//	cout << "dp." << i << "." << j << " = " << dp[i][j] << endl;
		}
	}
	printf("%.9lf", ans);
}


/*
3
2 2 2
5 5 5
5 5 5
*/