Educational Codeforces Round 97 F. Emotional Fishermen

给出一个长度为n~(2\leq n \leq 5000)的数组a_1,a_2,a_3,...,a_n~(1\leq a_i \leq 10^9),求有多少种将a重新排列后的b满足对\forall~ 2 \leq i \leq n都有b_i \geq 2max\{b_1,b_2,...,b_{i-1} \}2b_i \leq max\{b_1,b_2,...,b_{i-1} \}

先将数组a升序排序。用f[i][j]表示最大值为a[i]长度为j的序列总数。考虑如下两种转移:

  • 在序列末尾加入一个大于两倍最大值的数,f[k][j+1] \leftarrow f[i][j]a_k \geq 2a_i,实现时使用前缀和优化
  • 从满足2a_k \leq a_i且未在序列中的数a_k中选择一个加入序列末尾,f[i][j+1] \leftarrow f[i][j] * (k - j + 1),其中k表示最大的k满足2a_k \leq a_i

时间复杂度O(n^2)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5010;
const int mod = 998244353;
int a[maxn]; 
int sum[maxn][maxn], f[maxn][maxn];
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int t = 0; sum[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        while (2 * a[t + 1] <= a[i]) t++;
        for (int j = 1; j <= i; j++) {
            f[i][j] = sum[t][j - 1];
            if (j - 1 <= t) {
                (f[i][j] += 1ll * f[i][j - 1] * (t - j + 2) % mod ) %= mod;
            }
        }
        for (int j = 0; j <= i; j++)
            sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
    }
    cout << f[n][n] << endl;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>