题目大意,给出n个人的分数，积分差为k为同一组，问不能在同一组最多有多少人。
想法，可以分成以0到k-1分组，每组的公差是k，算出每组可以保证不是积分差为k的最大人数，最后统计累加即是答案。
用cnt记录一个分数的人数，val记录在每一组的每一个分数的人数，
dp[j]=max(dp[j-1],dp[j-2]+val[j]);特判一下第一个和第二个的情况。
代码如下
#include<bits/stdc++.h> using namespace std; const int maxsize=100000; int cnt[maxsize+5]; int val[maxsize+5]; int dp[maxsize+5]; int main() { int n,k,m,j,ans=0;cin>>n>>k; for(int i=0;i<n;i++){ cin>>m; cnt[m]++; } if(k==0){ for(int i=0;i<maxsize;i++) if(cnt[i])ans++; } for(int i=0;i<k;i++){ int m=0; for(int j=i;j<=maxsize;j+=k){ val[m++]=cnt[j]; } dp[0]=val[0]; dp[1]=max(dp[0],val[1]); for(int j=2;j<m;j++){ dp[j]=max(dp[j-1],dp[j-2]+val[j]); } ans+=dp[m-1]; } cout<<ans<<endl; }
原文：https://www.cnblogs.com/mohari/p/12940420.html
