ABC-403-D - Forbidden Difference · znzryb
## 思路讲解
这道题目，可以通过转化，变为给你一张链图，问你如何删去权重之和最少的点，使这张链图完全不联通。
这个问题可以通过dp解决。
```cpp
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](https://atcoder.jp/contests/abc403/submissions/65403420)
::: 源代码
```cpp
// 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，最后发现是循环范围出了问题
::: 源代码
```cpp
// 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;
}
/*
*/
```
:::