题意:
有 \((n\le 5000)\) 个渔民,每个渔民钓了一条重 \(a_i\) 的鱼,渔民按任意顺序展示他们的鱼。
若当前渔民的鱼的重量为 \(x\),之前展示过的鱼的最大重量 \(y\)。
一个排列满足条件当且仅当对于每个 \(x\),满足 \(2y\le x\) 或 \(2x\le y\)。
问有多少个排列满足条件,对 \(998244353\) 取模
分析:
做法一:
显然对于一个数列,重要的只有最大值。
所以首先从小到大排序,使用 dp。
记 \(f_{i,j}\) 表示当前排列填了 \(j\) 个数,其中最大值为 \(a_{i}\) 的方案数。记 \(lim_{i}=j\) 表示最大的 \(j\) 使得 \(2a_{j}\le a_{i}\)。
转移也很简单:
-
第 \(j\) 个数大于等于前面的最大值的 \(2\) 倍。直接枚举之前的最大值 \(a_{k}\),那么 \(f_{k,j-1} \rightarrow f_{i,j}(2a_{k} \le a_{i})\)。
-
第 \(j\) 个数小于等于前面的最大值的 \(\frac{1}{2}\)。前面已经用了 \(j-2\) 个数,有 \(lim_{i}\) 个数可以成为第 \(j\) 个数,因此有 \((j-2-lim_{i})\) 种。那么 \(f_{i,j-1} \times (j-2-lim_{i}) \rightarrow f_{i,j}\)。
前者很好使用前缀和优化,因此时间复杂度为 \(O(n^2)\)。
做法二:
容易发现排序后如果 \(2a_{n-1}>a_{n}\),那么答案必定为 \(0\)。
因此不妨记 \(f_{i}\) 表示当前最大值为 \(a_i\),序列里填了 \(lim_{i}+1\) 个数的方案数。
考虑枚举上一个最大值 \(j\),注意需要满足 \(2a_{j}\le a_{i}\),由于 \(lim_{j}+1\) 个位置已经固定了,将 \(i\) 放在第一个空位上,那么只剩 \(n-lim_{j}-2\) 个空位,将 \(lim_{i}-lim_{j}-1\) 个数填进去。因此转移为
\[f_{i}=\sum_{j=0}^{lim_{i}}f_{j} \times P_{n-lim_{j}-2}^{lim_{i}-lim_{j}-1} \]利用前缀和优化,时间复杂度 \(O(n \log n)\)。
标签:le,题解,最大值,个数,渔民,2a,lim,Fishermen,Emotional From: https://www.cnblogs.com/xcs123/p/17967026