Flip Machines

题目描述

有 $N$ 张编号为 $1$ 到 $N$ 的卡片。 每张卡片的一面写有一个整数；第 $i$ 张卡片的正面写着 $A_i$，背面写着 $B_i$。 最初，所有卡片都是正面朝上。 有 $M$ 台编号为 $1$ 到 $M$ 的机器。 机器 $j$ 有两个（不一定不同的）整数 $X_j$ 和 $Y_j$，它们在 $1$ 到 $N$ 之间。如果你启动机器 $j$， 它以概率 $\frac{1}{2}$ 翻转卡片 $X_j$，以剩余的概率 $\frac{1}{2}$ 翻转卡片 $Y_j$。 每次启动的这种概率是相互独立的。 Snuke 将执行如下过程。

选择一个由 $1$ 到 $M$ 的整数构成的集合 $S$。 按照集合中元素的升序，对应地依次启动这些编号的机器。

在 Snuke 可能选择的 $S$ 中，找出在该过程后卡片正面朝上的一面所写整数之和的最大期望值。

输入格式

输入由标准输入按以下格式给出： $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$

输出格式

输出答案。 如果你的输出与真实值的绝对或相对误差不超过 $10^{-6}$，则认为是正确的。

3 1
3 10
10 6
5 2
1 2

19.500000

1 3
5 100
1 1
1 1
1 1

100.000000

8 10
6918 9211
16 1868
3857 8537
3340 8506
6263 7940
1449 4593
5902 1932
310 6991
4 4
8 6
3 5
1 1
4 2
5 6
7 5
3 3
1 5
3 1

45945.000000

提示

$1\leq N \leq 40$ $1\leq M \leq 10^5$ $1\leq A_i,B_i \leq 10^4$ $1\leq X_j,Y_j \leq N$ 所有输入值均为整数。如果选择 $S$ 为空集，则不启动任何机器，因此过程后卡片正面朝上的一面所写整数之和的期望是 $3+10+5=18$。 如果选择 $S=\lbrace 1 \rbrace$，则启动机器 $1$。

如果卡片 $X_1 = 1$ 被翻转，过程后卡片正面朝上的一面所写整数之和是 $10+10+5=25$ 的期望值。 如果卡片 $Y_1 = 2$ 被翻转，过程后卡片正面朝上的一面所写整数之和是 $3+6+5=14$ 的期望值。

因此，期望值为 $\frac{25+14}{2} = 19.5$。 因此，过程后卡片正面朝上的一面所写整数之和的最大期望值是 $19.5$。
不同的机器可能具有相同的 $(X_j,Y_j)$。

标签: AtCoder|abc313F

来源

AtCoder|abc313F