Description：

一个游戏包含 $n$ 个小游戏，第 $i$ 个游戏有 $(1000-X[i]-Y[i])/1000$ 的概率失败， $X[i]/1000$ 的概率得一颗星， $Y[i]/1000$ 的概率得两颗星，游戏通关的要求是通过所有游戏并获得至少 $m$ 颗星，求打游戏次数的期望。

$1\le n \le 2000$

Solution：

由错位相减法可得：获得星星的期望是 $\frac 1{X[i]+Y[i]}$ ，获得两星的期望是 $\frac 1{Y[i]}$ ，获得且获得一星的概率是 $\frac{X[i]}{X[i]+Y[i]}$ ，获得且获得两星的概率是 $\frac {Y[i]}{X[i]+Y[i]}$ ，把 $y$ 按从小到大排序，最终结果一定是选一个前缀打到一颗星，剩下的打到两颗星。于是维护一个后缀期望和，并令 $f[i][j]$ 表示打了 $i$ 个获得了 $j$ 颗星的期望， $g[i][j]$ 表示对应概率。由于 $f$ 表示的是已经除掉了概率剩下的期望，即最后答案可以直接累加 $f$ ，所以每进行一步转移，就要先加上这步的期望乘到这个点的概率，在乘上这个转移的概率。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2010

double f[MAXN][MAXN << 1],g[MAXN][MAXN << 1];

double s1[MAXN],s2[MAXN],p1[MAXN],p2[MAXN],ans = 0;

int x[MAXN],y[MAXN],d[MAXN];

bool cmp(int a,int b){return y[a] < y[b];}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d%d",&x[i],&y[i]);

	for(int i = 1;i <= n;++i)d[i] = i;

	sort(d + 1,d + 1 + n,cmp);

	for(int i = 1;i <= n;++i)

	{

		int k = d[i];

		s1[i] = 1000 / double(x[k] + y[k]);

		s2[i] = 1000 / double(y[k]);

		p1[i] = double(x[k]) / double(x[k] + y[k]);

		p2[i] = double(y[k]) / double(x[k] + y[k]);

	}

	for(int i = n - 1;i >= 1;--i)s2[i] += s2[i + 1];

	ans = 0;

	f[0][0] = 0;g[0][0] = 1;

	for(int i = 0;i < n;++i)

	{

		for(int j = 0;j <= i * 2;++j)

		{

			if((n - i) * 2 == m - j)

				ans += g[i][j] * s2[i + 1] + f[i][j];

			else

			{

				f[i + 1][j + 1] += (f[i][j] + s1[i + 1] * g[i][j]) * p1[i + 1];

				g[i + 1][j + 1] += g[i][j] * p1[i + 1];

				f[i + 1][j + 2] += (f[i][j] + s1[i + 1] * g[i][j]) * p2[i + 1];

				g[i + 1][j + 2] += g[i][j] * p2[i + 1];

			}

		}

	}

	for(int i = m;i <= 2 * n;++i)ans += f[n][i];

	printf("%.7lf\n",ans);

	return 0;

}