题解：AT_abc403_d [ABC403D] Forbidden Difference

· · 题解

先排序。

考虑到只有差为 d 的两个数会被影响到，所以我们可以分别对模 d 同余的这 d 个集合分别统计答案。

题目要求删去最少的数，我们可以求保留最多的数，再去用 n 去减，这个东西可以用线性 dp 求解。

我们用 dp_{i,0/1} 表示这个位置删不删，则有以下 dp 式子：

dp_{i,0}=\max(dp_{i-1,0},dp_{i-1,1}) dp_{i,1}=\max(dp_{i-1,0}+sum_i,dp_{i-1,1})

其中 sum_i 表示 a_i 的数量。

注意特判 d=0 的情况。

以下是赛时代码。

#include<bits/stdc++.h>

using namespace std;

int n,d;
int a[1000010];
int ans[2];
int sum;
int b[1000010];
int aaa;
int f[1000010][2];

vector<int>v[1000010];

signed main(){
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]]++;
    }
    sort(a+1,a+1+n);
    for(int i=0;i<=1000000;i++){
        if(b[i]) aaa+=b[i]-1;
    }
    if(d==0){
        cout<<aaa;
        //assert(d!=0);
        return 0;
    }
    n=unique(a+1,a+1+n)-a-1;
    //printf("aa %d\n",n);
    for(int i=1;i<=n;i++){
        v[a[i]%d].push_back(a[i]);
    }
    for(int x=0;x<d;x++){
        if(v[x].size()==0) continue;
        f[0][0]=0;
        f[0][1]=b[v[x][0]];
        int qsu=b[v[x][0]];
        for(int i=1;i<v[x].size();i++){
            if(v[x][i]-v[x][i-1]==d){
                f[i][0]=max(f[i-1][0],f[i-1][1]);
                if(i>=2) f[i][1]=max(f[i-1][0],f[i-2][1])+b[v[x][i]];
                else f[i][1]=f[i-1][0]+b[v[x][i]];
            }
            else{
                f[i][0]=max(f[i-1][0],f[i-1][1]);
                f[i][1]=f[i][0]+b[v[x][i]];
            }
            qsu+=b[v[x][i]];
        }
        int bbb=max(f[v[x].size()-1][1],f[v[x].size()-1][0]);
        sum+=qsu-bbb;
        //printf("qwqwqwq %d %d\n",qsu,bbb);
    }
    cout<<sum;
    return 0;
}