codeforces1188C Array Beauty（DP/前缀和）

雀食是DP好题，DP玄学优化呜呜。

题目链接：codeforces 1188C

题目思路：

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

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

这里优化参考dalao，具体做法是优化 dp 范围。长度为 $k$ 的子序列最大差值为 $(k-1)\ast x$，而美丽值最大值是 $a[n]$，故现在只要求 $x\le a[n]/(k-1)$ 的范围即可，时间复杂度为 $O(n\ast a[n])$。

参考代码：

#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;
}