Codeforces 1189F. Array Beauty

首先可以注意到序列里面元素的顺序对答案是没有影响的，所以二话不说先排序再看看怎么搞

考虑枚举每种子序列可能产生的贡献并算一下产生这个贡献的子序列有多少

考虑设 $F(x)$ 表示选择的元素差值至少为 $x$ 的长度为 $k$ 的子序列的方案数

那么最终如果直接把每个 $F(x),x \in [1,max(a)]$ 加起来会发现，对于任意一种差值为 $t$ 的方案，它都被所有 $x<=t$ 的 $F(x)$ 各计算到了一次，那么总贡献即为 $t$，所以只要求出 $F$ 然后加起来就是我们要的答案

先不考虑复杂度，那么这个显然是可以 $dp$ 的，设 $f[i][j]$ 表示长度为 $i$ ，考虑了前 $j$ 个位置，第 $j$ 个位置强制选择时的子序列方案数

那么有转移 $f[i][j]+=f[i-1][k]$ 其中 $k<j$ 并且 $a_j-a_k>=x$ （注意这时 $a$ 已经按从小到大排序了）

注意到随着 $j$ 的增加，合法的 $k$ 一定是越来越大的并且是一段前缀区间，那么转移显然可以维护一个指针和一个前缀和加速到 $O(1)$

现在单次 $dp$ 的复杂度就是优秀的 $nk$ 了，那么再考虑一下枚举 $x$ 的复杂度，很好，复杂度达到了优秀的 $max(a)nk$

然后注意到一个看似微不足道的优化：枚举 $x$ 的时候如果 $x>max(a)/k+1$ ，那么一定不存在合法的长度为 $k$ 的序列了（显然吧）

发现复杂度就变成了 $\frac {max(a)} {k+1}nk$ 即 $max(a)n$ ...

然后就过了......

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=,mo=;

inline int fk(int x) { return x>=mo ? x-mo : x; }

int n,m,A[N];

int f[N][N],ans;

int main()

{

    n=read(),m=read();

    for(int i=;i<=n;i++) A[i]=read();

    sort(A+,A+n+); int mx=A[n];

    for(int I=;I<=mx/(m-);I++)

    {

        for(int i=;i<=n;i++) f[][i]=;

        for(int i=;i<=m;i++)

        {

            int sum=,p=;

            for(int j=;j<=n;j++)

            {

                while(A[p]+I<=A[j])

                    sum=fk(sum+f[i-][p++]);

                f[i][j]=sum;

            }

        }

        for(int i=;i<=n;i++) ans=fk(ans+f[m][i]);

    }

    printf("%d\n",ans);

    return ;

}

巴特西

Codeforces 1189F. Array Beauty

最新文章

热门文章