输出答案时, 小数点后第六位后的全部去掉, 不要四舍五入.
(题目太简洁,不需要大意)
这道题和 poj 的 Collecting Bugs 有些类似,一样是倒推。
用 f[i][j] 表示 i 张红牌和 j 张黑白时的最优答案。
对于初值显然有 f[i][0] = 0 ,对于转移,根据题目意思转移就好了,考虑是摸到红牌还是黑牌,然后和 0 取 max。
- /**
- * bzoj
- * Problem#1419
- * Accepted
- * Time: 1388ms
- * Memory: 1368k
- */
- #include < bits / stdc++.h > using namespace std;#define smax(_a, _b) _a = (_a > _b) ? (_a) : (_b)
- const int N = 5005;
- int R,
- B;
- double f[2][N];
- inline void init() {
- scanf("%d%d", &R, &B);
- }
- inline void solve() {
- int t = 0;
- for (int i = 1; i <= R; i++) {
- t ^= 1;
- f[t][0] = i;
- for (int j = 1; j <= B; j++) {
- f[t][j] = (f[t ^ 1][j] + 1.0) * i + (f[t][j - 1] - 1.0) * j;
- f[t][j] /= i + j;
- if (f[t][j] < 0) f[t][j] = 0;
- }
- }
- printf("%.6lf", f[t][B] - 5e-7);
- }
- int main() {
- init();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2431214.html