题解：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

的情况。

以下是赛时代码。

CPP

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

题解：AT_abc403_d [ABC403D] Forbidden Difference

文章操作

相关推荐

评论

题解：AT_abc403_d [ABC403D] Forbidden Difference