Description

小K不慎被LL邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。

他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前OIer，小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连Spaly都敲不对了，因此，希望你能帮帮小K，让他感受一下当欧洲人是怎样的体验。

本题中我们将考虑游戏的一个简化版模型。

玩家有一套卡牌，共$n$张。游戏时，玩家将$n$张卡牌排列成某种顺序，排列后将卡牌按从前往后依次编号为$1 \sim n$。本题中，顺序已经确定，即为输入的顺序。

每张卡牌都有一个技能。第$i$张卡牌的技能发动概率为$p_{i}$，如果成功发动，则会对敌方造成$d_{i}$点伤害。也只有通过发动技能，卡牌才能对敌方造成伤害。基于现实因素以及小K非洲血统的考虑，$p_{i}$不会为$0$，也不会为$1$，即$0<p_{i}<1$。

一局游戏一共有$r$轮。在每一轮中，系统将从第一张卡牌开始，按照顺序依次考虑每张卡牌。在一轮中，对于依次考虑的每一张卡牌：

$1$如果这张卡牌在这一局游戏中已经发动过技能，则

$1.1$ 如果这张卡牌不是最后一张，则跳过之（考虑下一张卡牌）；

否则（是最后一张），结束这一轮游戏。

$2$否则（这张卡牌在这一局游戏中没有发动过技能），设这张卡牌为第 i 张

$2.1$将其以$p_{i}$的概率发动技能。

$2.2$如果技能发动，则对敌方造成$d_{i}$点伤害，并结束这一轮。

$2.3$如果这张卡牌已经是最后一张（即$i$等于$n$），则结束这一轮；否则，考虑下一张卡牌。

请帮助小K求出这一套卡牌在一局游戏中能造成的伤害的期望值。

Input

输入文件的第一行包含一个整数$T$，代表测试数据组数。

接下来一共$T$组数据。

每组数据的第一行包含两个用空格分开的整数$n$和$r$，分别代表卡牌的张数和游戏的轮数。接下来$n$行，每行包含一个实数和一个整数，由空格隔开，描述一张卡牌。第$i$行的两个数为$p_{i}$和$d_{i}$，分别代表第$i$张卡牌技能发动的概率（实数）和技能发动造成的伤害（整数）。保证$p_{i}$最多包含$4$位小数，且为一个合法的概率。

Output

对于每组数据，输出一行，包含一个实数，为这套卡牌在这一局游戏中造成的伤害的期望值。对于每一行输出，只有当你的输出和标准答案的相对误差不超过$10^{-8}$时——即$\frac{\mid a-o \mid}{a} \le 10^{-8}$时(其中$a$是标准答案，$o$是输出)，你的输出才会被判为正确。

建议输出$10$位小数。

Sample Input

1

3 2

0.5000 2

0.3000 3

0.9000 1

Sample Output

3.2660250000

Hint

对于所有测试数据， $1 \le T \le 444,1 \le n \le 220,0 \le r \le 132，0 < pi < 1，0 \le d_{i} \le 1000$。

除非备注中有特殊说明，数据中$p_{i}$与$d_{i}$均为随机生成。

请注意可能存在的实数精度问题，并采取适当措施。

这题考试的时候状压dp都没有想到。

正解是一个更为神奇的dp，对于每张卡牌独立算贡献。如果第$i$张牌发动的概率为$P_{i}$,那么$$ans = \sum_{i=1}^{n}P_{i}d_{i}$$

怎么求$P_{i}$？将$r$轮看做$r$次机会，$f_{i,j}$表示考虑完第$i$张卡牌，还剩$j$轮的概率。转移$$f_{i,j-1}=f_{i,j-1}+f_{i,j} \times (1-p_{i+1})^{j}$$$$f_{i+1,j-1} = f_{i+1,j-1}+f_{i,j} \times (1-(1-p_{i+1})^{j})$$

其中$$(1-(1-p_{i+1})^{{j})=p_{i+1}\sum_{k=0}}{j-1}(1-p_{i+1})^{k}$$

dp初始状态$f_{0,r}=1$。有了这个dp之后我们就可以算出$P_{i}$了$$P_{i}=\sum f_{i-1}{j+1} \times (1-(1-p_{i})^{j+1} $$

在转移的时候记录即可。

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

#define maxn (230)

int n,r,d[maxn]; double p[maxn],P[maxn],ans,f[maxn][maxn],ci[maxn][maxn];

inline void dp()

{

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

	{

		ci[i][0] = 1;

		for (int j = 1;j <= r;++j) ci[i][j] = ci[i][j-1]*(1-p[i]);

	}

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

	f[0][r] = 1;

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

		for (int j = r;j >= r-i&&j >= 0;--j)

		{

			f[i+1][j] += f[i][j]*ci[i+1][j];

			if (j)

			{

				double t = f[i][j]*(1-ci[i+1][j]);

				f[i+1][j-1] += t; P[i+1] += t;

			}

		}

}

int main()

{

	freopen("4008.in","r",stdin);

	freopen("4008.out","w",stdout);

	int T; scanf("%d",&T);

	while (T--)

	{

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

		for (int i = 1;i <= n;++i) scanf("%lf %d",p+i,d+i);

		dp(); ans = 0;

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

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

	}

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

BZOJ 4008 亚瑟王