小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。 小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是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
10 1 2 1 1 1 1 4 4 3 4 4
8
思路 设共有x种分数，将其分为k组，每个分数满足相邻的分数值相差为k。正如样例2中所示，共有4种分数，将其分为1组：{1,2,3,4},这个组中任何相邻的两个分数都不能同时取，因为它们相差k，该分组还对应了一个人数分组：{4,1,1,4},要想使得人数尽量多，而且分数不能相差1，那么选择分数分别为{1,4},人数是4+4=8.
上述是只有一个分组的情况，当有多个分组的时候也是同样的处理方法–尽量选择不相邻且人数最多。对于一个人数分别为{a1,a2,…,an}的分组，可以利用动态规划算法来选择最多人数，且都不相邻。每个ai只有选择与不选择两种可能，假设dp(i)表示前i个人数能获得的最多人数，那么选择第i个人数的话，dp(i)=dp(i−2)+ai，如果不选择第i个人数的话，dp(i)=dp(i−1)，这样得到转移方程dp(i)=max{dp(i−1),dp(i−2)+ai}。
注意，当k=0的时候特殊处理一下。 代码如下：
#include<iostream> #include<algorithm> using namespace std; const int N = 1e5; int a[N + 10], sum[N + 10], dp[N + 10], b[N + 10]; int main() { int n, m; cin >> n>> m; for(int i = 0; i < n; i++){ cin >> a[i]; sum[a[i]]++; } int ans = 0; if(m == 0){ for(int i = 0; i <=N; i++ ) if(sum[i])ans++; } else{ for(int i = 0; i < m; i++){ int k = 0; for(int j = i; j <= N; j += m){ b[k++] = sum[j]; } dp[0] = b[0]; dp[1] = max(dp[0], b[1]); for(int j = 2; j < k; j++){ dp[j] = max(dp[j - 1], dp[j - 2] + b[j]); } ans += dp[k - 1]; } } cout << ans << endl; return 0; }