问题描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是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
解题思路：一开始看到是以分差为K分组匹配，想到的是用并查集将分差等于K的分为一组，这样每组之间都不会匹配，再从每组中选择一个最佳方案，把最优方案相加即可
得到一个最优解。但如何在并查集同一组中选择最优方案又成了问题。最后看到别的朋友的思路才知道用DP解决。我的代码主要和一位朋友的相似，所以附上链接https://blog.csdn.net/Helloirbd/article/details/88070674 我的代码只是用了《挑战程序设计竞赛》的风格重复了一遍。
可以用A数组保存积分 k （0<=k<=100000）出现的次数，将积分相差n*K的(0<=n<=Max_N/K) 的分为一组，这样就可以得到K组 （数值%K=0，1，...，K-1），在每一组中
用dp找到最优方案。dp[ i ]：某一组前 i 个的最优方案（这里有点难表述）。对于第 i 个有两种选择：选择和 i 位置相差 2*K的对手，这样第 i 个位置的选手也符合条件; 或者选择和
位置 i 积分相差K的选手，这是位置 i 的选手不符合条件。体现在代码中：dp[ i ] = max ( dp[ i -2 ] + cnt[ i ], dp[ i-1 ] )
实现代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int Max_N = 100000; 7 const int Max_K = 100000; 8 //输入 9 int N,K; 10 int A[Max_N+1];//A[i]:数值i出现了多少次 11 12 void solve() 13 { 14 int sum = 0; 15 if( K==0 )//K==0时单独考虑 16 { 17 for(int i=0; i<=Max_K; i++){ 18 if( A[i] ) sum++; //相同积分作为匹配的一组,只能选一人 19 } 20 printf("%d ",sum); 21 return; 22 } 23 for(int i=0; i<K; i++)//分为K组 24 { 25 int cnt[Max_K/K+1];//积分为相差n*K的一组 26 int dp[Max_K/K+1];//dp数组 27 memset(dp,0,sizeof(dp));//初始化值为0 28 29 int k = 0; 30 for(int j=i; j<=Max_K; j+=K ) 31 { 32 cnt[k++] = A[j];//其中一组 33 } 34 35 dp[0] = cnt[0]; 36 dp[1] = cnt[1];//前两个单独考虑 (i-2>=0) 37 for(int j=2; j<k; j++) 38 { 39 dp[j] = max( dp[j-2]+cnt[j], dp[j-1]); 40 } 41 sum += dp[k-1]; 42 } 43 printf("%d ",sum); 44 } 45 46 int main() 47 { 48 scanf("%d%d",&N,&K); 49 while( N-- ) 50 { 51 int a; 52 scanf("%d",&a); 53 A[a]++; 54 } 55 56 solve(); 57 58 return 0; 59 }
/*(注释)：如果有朋友看到的话，希望可以给我的表述提出自己的意见，或者可以一起学习进步。