蓝桥杯2017年第八届真题-对局匹配 （C++代码）自用mark

解题思路:

先自己用着先把，AC是AC了，可是还有一些地方有点模糊，过后看了...

去看别人的题解吧....

参考代码:

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=100005;
int n,k,max_score=INT_MIN;
int ans=0;
int a[maxn]= {0}; //人数
int hash_[maxn]= {0}; //分数
int dp[maxn]= {0}; //动态规划
int cnt[maxn]= {0}; //取分差用的
int main() {
 hh;
 cin>>n>>k;
 for(int i=0; i<n; i++) {
  cin>>a[i];
  hash_[a[i]]++;
  if(max_score<a[i]) {
   max_score=a[i];
  }
 }
 if(k==0) { //特判
  for(int i=0; i<=max_score; i++) {
   if(hash_[i]>0) {
    ans++;
   }
  }
  cout<<ans<<endl;
  exit(0); //quit out
 }
 for(int i=0; i<k; i++) {
  int pos=0;
  for(int j=i; j<maxn; j+=k) {
   cnt[pos++]=hash_[j];
  }
  dp[0]=cnt[0];
  for(int j=0; j<pos; j++) {
   if(j==1) {
    dp[j]=max(dp[j-1],cnt[j]);
   } else {
    dp[j]=max(dp[j-1],dp[j-2]+cnt[j]);
   }
  }
  ans+=dp[pos-1];
 }
 cout<<ans<<endl;
 return 0;
}