CF1188 C.Array Beauty【动态规划】

题目链接：codeforces 1188C

题解

美丽值与顺序无关，故对数组排序，子序列的美丽值就是所有相邻数的差值的最小值。

设美丽值为 的子序列个数为 cnt[x]，那么美丽值为 的子序列个数为 cnt[1]，它对答案的贡献为 cnt[1]*1，相似的，美丽值为 的子序列对答案的贡献为 cnt[2]*2，差值的最大值为 ，故最后的答案为： 不难发现答案就是 cnt 的后缀和 suf的和，suf[i] 表示美丽值不小于 的方案数。于是，我们可以枚举美丽值 。令 dp[i][j] 为最后一位为 ，长度为 ，差值不小于 的子序列。定义状态转移方程： 因为 是递增的，所以用前缀和求这个 ，最后算出的 dp[n][k] 就是美丽值不小于 的方案数。时间复杂度为 。

可优化 dp 范围。长度为 的子序列最大差值为 ，而美丽值最大值是 ，故现在只要求 的范围即可，时间复杂度为 。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const int mod = 998244353;
ll a[N], dp[N][N], pre[N][N];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+1+n);
    a[0] = -0x3f3f3f3f;
    ll ans = 0;
    for (int x = 1; x * (k-1) <= a[n]; x++) {
        dp[0][0] = 1, pre[0][0] = 1;
        int now = 0, res = 0;
        for (int i = 1; i <= n; i++) {
            while (x <= a[i] - a[now]) now++;
            for (int j = 0; j <= k; j++) {
                if (j) dp[i][j] = pre[now-1][j-1];
                pre[i][j] = (pre[i-1][j] + dp[i][j]) % mod;
            }
            res = (res + dp[i][k]) % mod;
        }
        ans = (ans + res) % mod;
    }
    cout << ans << endl;
    return 0;
}