题意:

$n$场比赛

打第i场加 $a_{i}$ 经验，且打完获得当前经验 * $b_{i}$ 的奖金

打完$n/2$场获得$x$的经验(保证$n$为偶数)

任意安排顺序，求最大奖金

$b_i<=10,n<=50,x和a_i<=10^5$

题解:

1 dp(标算)

如果不考虑$x$的话是可以贪心的。

因为考虑相邻两个$a_1,b_1,a_2,b_2$

交换后的变化=$a_2*b_1-a_1*b_2$

所以交换更优<=>$a_2/b_2>a_1/b_2$

只有$a/b$降序时无法交换，达到最优

所以$1..n/2$场与$n/2+1..n$场都是按$a/b$降序的。

按$a/b$降序排序后

枚举$n/2+1..n$场的$b_i$的和

然后dp，记录打了前几场，有几场在后面一半打，以及后面一半打的$b_i$的和。

复杂度$O(n^4*b^2)$ ，常数较小

2 随机化

先按$a/b$降序排序

然后考虑随机哪些点在后面一半打之后就可以贪心了

先让在后面一半的在后面一半打作为初始解

每次随机交换一个在前面的和在后面的

退火，甚至只有更优才交换，都能过。。

可以极快ac。

我目前也不知道怎么卡。。。

3 贪心+枚举

注意到$b$很小，而$b$一样的必定要让$a$大的在前面

(其实一开始想的是利用这一点暴力dp，但发现状态数会达到6^10，时空都炸)

利用这一点，暴力枚举每个$b$在后面$n/2$个占几个 然后在$O(n)$检验

最差情况下就是每个$b$都有$5$的$a$，差不多要枚举$10^7$次

勉强能过吧