ABC-403-D - Forbidden Difference

思路讲解

这道题目，可以通过转化，变为给你一张链图，问你如何删去权重之和最少的点，使这张链图完全不联通。

这个问题可以通过dp解决。

dp[0][0]=0,dp[0][1]=ls.front();
FOR(j,1,SZ(ls)-1){
	// 当前带着的=之前不带的 之前带着砍掉之前带着的
	dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
	// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
	dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
}
ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);

AC代码

https://atcoder.jp/contests/abc403/submissions/65403420

源代码

// Problem: D - Forbidden Difference
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,D,K,T,A[MAXN];
// arr uA[MAXN];
ll Cnt[MAXN];
ll vis[MAXN];
ll dp[MAXN][2];

inline void solve(){
	cin>>N>>D;
	// list<ll> ls;
	FOR(i,1,N){
		cin>>A[i];
		++Cnt[A[i]];
		// ls.pb(A[i]);
	}
	// assert(D!=0);
	if(D==0){
		ll ans=0;
		FOR(i,0,MAXN-5){
			if(Cnt[i]) ++ans;
		}
		cout<<N-ans<<"\n";
		return;
	}
	// ll up=-INF,idx=0;
	// FOR(i,1,N){
		// if(up!=A[i]){
			// uA[++idx][0]=A[i];
			// uA[idx][1]=1;
			// up=A[i];
		// }else{
			// ++uA[A[i]][1];
		// }
	// }
	ll ans=0;
	FOR(i,0,MAXN-1-D){
		if(Cnt[i]==0) continue;
		if(Cnt[i+D]==0) continue;
		if(vis[i]) continue;
		vector<ll> ls;
		for(int j=i;j<=MAXN-1;j+=D){
			if(Cnt[j]) ls.pb(Cnt[j]),vis[j]=true;
			else break;
		}
		// ll oddC=0,evenC=0;
		// FOR(j,0,SZ(ls)-1){
			// if(j%2==0) evenC+=ls[j];
			// else oddC+=ls[j];
		// }
		// ans+=min(oddC,evenC);
		
		// dp[][0]表示带着这个（序号为i）的最小，dp1表示不带这个的最小消耗
		dp[0][0]=0,dp[0][1]=ls.front();
		FOR(j,1,SZ(ls)-1){
			// 当前带着的=之前不带的 之前带着砍掉之前带着的
			dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
			// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
			dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
		}
		ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);
	}
	ans=min(ans,N);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC 
https://atcoder.jp/contests/abc403/submissions/65403420
*/

心路历程（WA，TLE，MLE……）

WA，最后发现是循环范围出了问题

源代码

// Problem: D - Forbidden Difference
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,D,K,T,A[MAXN];
// arr uA[MAXN];
ll Cnt[MAXN];
ll vis[MAXN];
ll dp[MAXN][2];

inline void solve(){
	cin>>N>>D;
	// list<ll> ls;
	FOR(i,1,N){
		cin>>A[i];
		++Cnt[A[i]];
		// ls.pb(A[i]);
	}
	// assert(D!=0);
	if(D==0){
		ll ans=0;
		FOR(i,0,MAXN-5){
			if(Cnt[i]) ++ans;
		}
		cout<<N-ans<<"\n";
		return;
	}
	// ll up=-INF,idx=0;
	// FOR(i,1,N){
		// if(up!=A[i]){
			// uA[++idx][0]=A[i];
			// uA[idx][1]=1;
			// up=A[i];
		// }else{
			// ++uA[A[i]][1];
		// }
	// }
	ll ans=0;
	FOR(i,0,MAXN-1-D){
		if(Cnt[i]==0) continue;
		// if(Cnt[i+D]==0) continue;
		if(vis[i]) continue;
		vector<ll> ls;
		for(int j=i;j<=MAXN-1-D;j+=D){
			if(Cnt[j]) ls.pb(Cnt[j]),vis[j]=true;
			else break;
		}
		// ll oddC=0,evenC=0;
		// FOR(j,0,SZ(ls)-1){
			// if(j%2==0) evenC+=ls[j];
			// else oddC+=ls[j];
		// }
		// ans+=min(oddC,evenC);
		
		// dp[][0]表示带着这个（序号为i）的最小，dp1表示不带这个的最小消耗
		dp[0][0]=0,dp[0][1]=ls.front();
		FOR(j,1,SZ(ls)-1){
			// 当前带着的=之前不带的 之前带着砍掉之前带着的
			dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
			// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
			dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
		}
		ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);
	}
	ans=min(ans,N);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/