ABC-470-E - Concentration （翻牌配对）

题目大意

翻牌配对

时限 2000 ms，内存 1024 MB。

给定整数 $N, L$ 以及 $N$ 个两两不同的整数 $A_1, A_2, \dots, A_N$。

桌上共有 $2N$ 张牌，每个数值 $A_i$ 恰好写在其中两张牌的正面上，牌的背面没有任何信息。

初始时把所有牌随机洗乱后背面朝上摆放。等价地说：设 $B$ 是把序列 $(A_1, A_1, A_2, A_2, \dots, A_N, A_N)$ 均匀随机打乱后得到的长度为 $2N$ 的序列，则第 $i$ 张牌正面的数字为 $B_i$。

玩家知道所有的 $A_i$，但最初不知道任何 $B_i$。一旦某张牌 $i$ 被翻开，玩家就会永久记住 $B_i$ 的值。

游戏开始时，生命值为 $L$，得分为 $0$，尚未被移除的牌的下标集合为 $S = \{1, 2, \dots, 2N\}$。玩家在任何时刻都知道当前的生命值、得分和集合 $S$。

重复执行以下步骤，直到生命值变为 $0$ 或者 $S$ 为空：

1. 玩家根据当前已知信息，从 $S$ 中选择一张牌 $i$ 并翻开，获知 $B_i$。

2. 玩家根据当前已知信息（包括刚获知的 $B_i$），从 $S \setminus \{i\}$ 中选择一张牌 $j$ 并翻开，获知 $B_j$。

3. 若 $B_i = B_j$，则把 $i, j$ 从 $S$ 中移除，并把得分增加 $B_i$。

4. 若 $B_i \neq B_j$，则把这两张牌翻回背面，并把生命值减少 $1$。

玩家以最大化最终得分的期望值为目标采取最优策略。请求出游戏结束时的期望得分。

输入从标准输入按以下格式给出：

第一行两个整数 $N$ 和 $L$。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出一行一个实数，表示最优策略下游戏结束时的期望得分。答案与标准答案的绝对误差或相对误差不超过 $10^{-5}$ 即视为正确。

• $1 \leq N \leq 200$

• $1 \leq L \leq 200$

• $1 \leq A_1 < A_2 < \dots < A_N \leq 10^5$

• 所有输入值均为整数。

3 2
1 2 3

3.8666666667

游戏可能按如下方式进行。为了区分这六张牌，分别称它们为 A、B、C、D、E、F。

游戏以生命值 $2$、得分 $0$ 开始。

翻开卡牌 A，上面写着 $3$。
翻开卡牌 B，上面写着 $2$。
因为数字不同，把两张牌翻回背面，生命值减少 $1$，变为 $1$。

翻开卡牌 C，上面写着 $3$。
翻开卡牌 A，上面写着 $3$。
因为数字相同，把这两张牌移出桌面，得分增加 $3$，变为 $3$。

翻开卡牌 D，上面写着 $1$。
翻开卡牌 E，上面写着 $2$。
因为数字不同，把两张牌翻回背面，生命值减少 $1$，变为 $0$。

生命值变为 $0$，游戏结束，最终得分为 $3$。

注意，在上述过程中刚翻开卡牌 C 之后，玩家可以利用「卡牌 C 正面写着 $3$」这一信息，选择翻开另一张已经知道写着 $3$ 的卡牌 A。

5 2
2 3 5 7 101

17.8560846561

20 10
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

770.7122293087

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）