撰写问题描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。
现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, … AN。
小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？
输入格式
第一行包含两个个整数N和K。
第二行包含N个整数A1, A2, … AN。
对于30%的数据，1 <= N <= 10 对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000 输出格式 一个整数，代表答案。 样例输入 10 0 1 4 2 8 5 7 1 4 2 8 样例输出 6 题解： 直接按照0~k-1开头，每次+k分成k种序列，然后dp[i]=max(dp[i-2]+cnt[i],dp[i-1]),即默认选择了i-1,而选择i的时候就有两种转移方向。 cnt[i]代表原始输入中i出现的次数 有两个疑问： 1.因为我们将dp[i-1]都当作是选择了i-1,但是如果实际上并没选则i-1呢？会不会少了统计了cnt[i]? 不会，因为如果前面的没选择，状态实际上都是从i-2转移过来的。 2.如果中间出现断层，比如k=2，然后其中一个序列为1 3 5 9 11，会出现统计错误吗？ 不会，和前面一样，如果有断层，其实就相当于默认该选的i-1没有选中，而状态都是由前面的合法状态转移而来。 [cpp] #include<iostream> using namespace std; int book[100005],a[100005],dp[100005]; int main() { int i,j,n,k,t,x=0,ans=0; cin>>n>>k; for (i=0;i<n;i++) { cin>>t; book[t]++; } if (k==0) { for (i=0;i<100005;i++) { if (book[i]!=0) ans++; } cout<<ans; return 0; } else { for (i=0;i<k;i++) { x=0; for (j=i;j<100005;j+=k) a[x++]=book[j]; for (j=0;j<x;j++) { if (j==0) dp[0]=a[0]; else if (j==1) dp[1]=max(a[1],dp[0]); else dp[j]=max(dp[j-1],dp[j-2]+a[j]); } ans+=dp[x-1]; } } cout<<ans; } [/cpp] 另外，我还有一版的错误代码，能得62分，将dp[1][j]表示选择了第j个，dp[0][j]未选择第j个，再进行值域上的状态转移，最后用并查集找每个连续相差k的出最后一个元素，将该序列中能够同时出现的次数累加，但是不知道bug在哪。 [cpp] //#include<bits/stdc++.h> #include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B){ (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B){ (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int MAXN = 1e6+10; int f[3][200010]; int a[200100]; int cnt[200100]; int pre[200100]; int find(int x){ if(x==pre[x])return x; else return pre[x]=find(pre[x]); } set<int>s; int main(){ int n,k; scanf("%d%d", &n,&k); CLR(cnt); int m = 0; CLR(f); rep(i,1,n)scan_d(a[i]),cnt[a[i]]++,m=max(m,a[i]); rep(i,0,m){ pre[i]=i; } rep(i,0,k){ f[1][i]=cnt[i]; f[0][i]=0; if(cnt[i]&&cnt[i+k]){ pre[i]=i+k; } } int maxx=0; rep(i,k+1,m){ if(cnt[i])f[1][i]=max(f[1][i-k]-cnt[i-k]+cnt[i], f[0][i-k]+cnt[i]); if(cnt[i])f[0][i]=max(f[0][i-k],f[1][i-k]); if(cnt[i]&&cnt[i+k]){ pre[i]=i+k; } } rep(i,0,m){ if(cnt[i])s.insert(find(i)); } if(k==0){ cout<<s.size()<<endl; return 0; } set<int>::iterator it; for(it=s.begin();it!=s.end();it++){ maxx+=max(f[1][*it],f[0][*it]); } cout<<maxx<<endl; return 0; } [/cpp]