ABC-470-E - Concentration (翻牌配对) · znzryb
## 题目大意
### 翻牌配对
时限 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$。
1. 玩家根据当前已知信息(包括刚获知的 $B_i$),从 $S \setminus \{i\}$ 中选择一张牌 $j$ 并翻开,获知 $B_j$。
1. 若 $B_i = B_j$,则把 $i, j$ 从 $S$ 中移除,并把得分增加 $B_i$。
1. 若 $B_i \neq B_j$,则把这两张牌翻回背面,并把生命值减少 $1$。
玩家以最大化最终得分的期望值为目标采取最优策略。请求出游戏结束时的期望得分。
<!-- Notion block type: heading_4 -->
输入从标准输入按以下格式给出:
第一行两个整数 $N$ 和 $L$。
第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$。
<!-- Notion block type: heading_4 -->
输出一行一个实数,表示最优策略下游戏结束时的期望得分。答案与标准答案的绝对误差或相对误差不超过 $10^{-5}$ 即视为正确。
<!-- Notion block type: heading_4 -->
- $1 \leq N \leq 200$
- $1 \leq L \leq 200$
- $1 \leq A_1 < A_2 < \dots < A_N \leq 10^5$
- 所有输入值均为整数。
<!-- Notion block type: heading_4 -->
<!-- Notion block type: heading_4 -->
```
3 2
1 2 3
```
<!-- Notion block type: heading_4 -->
```
3.8666666667
```
<!-- Notion block type: heading_4 -->
游戏可能按如下方式进行。为了区分这六张牌,分别称它们为 `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`。
<!-- Notion block type: heading_4 -->
```
5 2
2 3 5 7 101
```
<!-- Notion block type: heading_4 -->
```
17.8560846561
```
<!-- Notion block type: heading_4 -->
```
20 10
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
```
<!-- Notion block type: heading_4 -->
```
770.7122293087
```
## 思路讲解
## AC代码
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)