Space Station - Problem

思路

你会受到 $n$ 次攻击，第 $i$ 次攻击的伤害为 $a_i$，其中 $a$ 是一个 $1\sim n$ 的排列。你可以让攻击发生并付出 $a_i$ 的代价，或者使用 $m$ 的代价让伤害不发生。求在最优策略下期望值的最小值。

其中数据范围满足，$1\le n,m\le 100$。

思路

设 $f_{i,j}$ 表示剩下 $i$ 个数且它们的和为 $j$ 的方案数，$f$ 数组的转移十分显然：

$\forall i \in [1,n]\cap\mathbb{Z},j\in[1,i]\cap\mathbb{Z},k\in[a_i,200\cdot i]\cap\mathbb{Z}~~~~f_{j,k}\gets f_{j,k}+f_{j-1,k-a _i}$

对于最优策略，显然在选择到 $p$ 的位置时，如果 $\dfrac{\sum\limits_{i=p+1}^n a_i}{n-p+2}>m$ 选择使用防御，反之吃下 $a_i$ 的代价。

根据期望的定义，可以得到答案为：

$\sum\limits_{i=1}^n\dfrac{\sum\limits_{j=i}^{200\cdot i}f_{i,j}\times \min(j,i\times m)}{i\times C_{n}^{i}}$