先介绍O(n^2)的做法(536ms)
显然棍子的重量与拿棍子是无关的。因此我们可以定义与重量无关的状态。
设类2棍子的总个数为m,f[i][j]为有i根类1棍子和j根类2棍子没拿时,把所有棍子都拿一遍,拿类2棍子的期望总次数。
f[i][j] = i / (i + m) f[i-1][j] + j / (i + m) f(i, j-1) + (m-j) / (i+m)
f[i][j] + m / (i + m)
f[i][j] = (i f[i-1][j] + j f[i][j-1] + m) / (i + j)
h[0] = 0; for (int i = 1; i < MAXN; ++i) { h[i] = h[i-1] + 1.0 / i; }
scanf("%d", &T); for (int Ti = 1; Ti <= T; ++Ti) { int n; scanf("%d", &n); double sum = 0; for (int i = 0; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); if (1 == b) { sum += a; } else { sum += h[n] * a; } } printf("Case %d: %.5f\n", Ti, sum); } return0; }