题解

思路

将鱼重排序。考虑已经安排了 $k$ 位渔夫，且其中最大鱼重是排序后的 $a_i$。除最大值外，所有已经出现的鱼都必须满足 $2a_j\le a_i$，否则它既不能成为新的至少翻倍最大值，也不能在当前最大值后变得难过。

小范围枚举排列；中等范围直接枚举动态规划的转移来源；满分算法用前缀和优化来源求和。

做法

令 $c_i$ 为满足 $2a_j\le a_i$ 的鱼的数量。设 $dp[i][k]$ 为长度为 $k$、当前最大鱼为 $a_i$ 的合法前缀数量。

加入下一条鱼有两种方式：

• 最大值仍为 $a_i$，从尚未使用且不超过 $a_i/2$ 的鱼中选一条，共有 $c_i+2-k$ 种；
• 新最大值变为 $a_i$，此前最大值可为任意下标小于 $c_i$ 的鱼，对这些 dp[j][k-1] 求和。

于是

$$dp[i][k]=dp[i][k-1](c_i+2-k)+\sum_{j<c_i}dp[j][k-1].$$

对第二维的上一层建立下标前缀和即可在 $O(1)$ 时间完成转移。答案为 $dp[n-1][n]$。

复杂度

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。