CF1188C Array Beauty

Codeforces Round #572 (Div. 2) 题解

题意

给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ，求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。

题解

利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数，那么答案就是 $\sum_{i=1}^\infty g(i)$ 。

先把序列从小到大排序，这样并不影响答案。可以发现美丽值最大为 $\dfrac{a_n}{k-1}$ ，所以只需要求 $\sum_{i=1}^{\frac{a_n}{k-1}} g(i)$ 。

$g(x)$ 可以用DP来求。用 $f[i][j]$ 表示子序列末尾为 $i$ ，选了 $j$ 个数，美丽值 $\geq x$ 的子序列个数。

可以不选 $i$ ，也可以用 $a[i]-a[k]\geq x$ 的最大的 $k$ 来转移，方程式为：

$$f[i][j]=f[i-1][j]+f[k][j-1]$$

随着 $i$ 增大，$k$ 也是单调不降的，所以直接用第二个指针得到 $k$ 即可。

#include<bits/stdc++.h>
#define ha 998244353

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,k,ans,a[1005],f[1005][1005];

signed main()
{
    n=read(); k=read();
    for (int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for (int i=0;i<=n;i++) f[i][0]=1;
    for (int x=1;x*(k-1)<=a[n];x++)
    {
        int pre=0; //即为 k
        for (int i=1;i<=n;i++)
        {
            for (;a[pre+1]<=a[i]-x;pre++);
            for (int j=1;j<=k;j++) f[i][j]=(f[i-1][j]+f[pre][j-1])%ha;
        }
        ans=(ans+f[n][k])%ha;
    }
    return !printf("%d",ans);
}