Description：

$n$ 张牌 $r$ 轮游戏，每张牌有 $p_i$ 的概率发动对敌方造成 $d_i$ 的伤害，每张牌只能用一次，每用一次即结束该轮，问整套牌期望能造成多少伤害。

$1\le testcases\le 444,1\le n \le 220,1\le r \le 132$

Solution：

一个一个牌推很难考虑每用一次即结束该轮这个要求，由期望的线性性得总期望 $\begin{align}=\sum_{i=1}^nfp[i]\times d[i]\end{align}$ ，即总发动概率乘伤害，设 $f[i][j]$ 表示考虑了前 $i$ 张牌共出了 $j$ 张牌的概率，那么可以得到 $\begin{align}fp[i]=\sum_{k=0}^{r-1}f[i-1][k]\times (1-(1-p[i])^{r-k})\end{align}$ ，后面那部分的含义是在轮到他的 $r-k$ 轮中他都没有被出出去的概率， $f[i][j]$ 的转移就是分别考虑第 $i$ 张牌最终出不出，如果出，那么 $f[i-1][j]\times (1-(1-p[i])^{r-j})\to f[i][j+1]$ ，如果不出，那么 $f[i-1][j]\times (1-p[i])^{r-j}\to f[i][j]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,r;

#define MAXN 230

#define MAXR 142

double f[MAXN][MAXR];

double p[MAXN],fp[MAXN];

int d[MAXN];

double power[MAXN][MAXR];

void work()

{

	memset(f,0,sizeof(f));

	f[0][0] = 1;

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

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

		scanf("%lf%d",&p[i],&d[i]);

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

	{

		power[i][0] = 1;

		for(int j = 1;j <= r;++j)

			power[i][j] = power[i][j - 1] * (1.0 - p[i]);

	}

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

	{

		for(int j = 0;j <= r;++j)

		{

			f[i][j + 1] += f[i - 1][j] * (1.0 - power[i][r - j]);

			f[i][j] += f[i - 1][j] * power[i][r - j];

		}

	}

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

	{

		fp[i] = 0;

		for(int j = 0;j < r;++j)

		{

			fp[i] += f[i - 1][j] * (1.0 - power[i][r - j]);

		}

	}

	double ans = 0;

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

	{

		ans += fp[i] * d[i];

	}

	printf("%.10f\n",ans);

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}