【Codeforces 1188C】Array Beauty | Mrsrz's blog

动态规划。

题目大意：

给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$，定义它的一个长度为 $k$ 的子序列 $b_1,b_2,b_3,\ldots,b_k$ 的价值为：

$$\min_{1\leq i\leq j\leq k}|b_i-b_j|$$

求 $a$ 的所有长度为 $k$ 的子序列的价值和。

题解：

首先这个价值和数的顺序是无关的，因此可以对 $a$ 进行排序，这样计算贡献就可以按照下面的式子计算：

$$\min_{i=1}^{k-1}(b_{i+1}-b_i)$$

下面的 $a$ 都默认有序。

由于一定要选 $k$ 个数，因此答案的上界 $m=\lceil\frac{a_n-a_1}{k-1}\rceil$。

我们考虑计算出答案为 $1\sim m$ 的所有方案数。

直接算不容易计算，考虑求出答案大于等于 $1\sim m$ 的方案数，然后差分计算。

我们令 $f_{i,j}$ 表示前 $i$ 个数中，选 $j$ 个数，相邻两个的差都大于当前的 $d$ 的方案数。

直接计算是 $O(n^3k)$ 的，可以用前缀和优化为 $O(n^2k)$。

我们发现，枚举 $d$ 计算时，$a_i$ 前面第一个和它相差大于等于 $d$ 的位置是单调的，所以可以用单调的指针维护这个位置，那么时间复杂度为 $O(nk)$。

总时间复杂度为 $O(\frac{V}{k}\cdot nk)=O(nV)$。

Code：

#include<cstdio>
#include<algorithm>
typedef long long LL;
const int N=1e3+6,md=998244353;
int f[N][N],g[N][N],n,k,a[N],pre[N],t[100005];
inline void upd(int&a){a+=a>>31&md;}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    std::sort(a+1,a+n+1);
    for(int v=(a[n]-a[1])/(k-1)+2;~v;--v){
        for(int i=1;i<=n;++i){
            f[i][1]=1,g[i][1]=i;
            while(pre[i]+1<i&&a[i]-a[pre[i]+1]>=v)++pre[i];
            for(int j=2;j<=i&&j<=k;++j)
            f[i][j]=g[pre[i]][j-1],upd(g[i][j]=g[i-1][j]+f[i][j]-md);
        }
        int&s=t[v];
        for(int i=k;i<=n;++i)upd(s+=f[i][k]-md);
    }
    int ans=0;
    for(int i=(a[n]-a[1])/(k-1)+1;i;--i)ans=(ans+(LL)i*(t[i]-t[i+1]+md))%md;
    printf("%d\n",ans);
    return 0;
}