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

解题思路:

注意事项:

#include <stdio.h>
#define M 100001
#define max(a,b) a>b?a:b
int score[M]={0};
int search(int k);
int main(void){
	int num=0,k=0;
	int i=0,j=0;
	scanf("%d %d",&num,&k);
	for(i=0;i<num;i++)
	{
		scanf("%d",&j);
		score[j]++;
	}
	printf("%d",search(k));
}
 int search(int k){
	int sum=0;
	int i=0,j=0;
	int val[M]={0},dp[M]={0};
	if(k==0)   //为０时特殊考虑
	{
		for(i=1;i<M;i++)
		{
			if(score[i]) sum++;
		}
	}
	else
	{
		for(i=0;i<k;i++)   //对ｋ组中的每一组进行遍历
		{
			int m=0;
			for(j=i;j<M;j+=k)  //记录这一组中的人数分布情况
			{
				val[m++] = score[j];
			}
			dp[0] = val[0];
			for(j=1;j<m;j++)  //对人数进行动态规划
			{
				if(j==1) dp[j] = max(dp[0], val[j]);  //０和１不能匹配，因为积分正好相差k
                else dp[j] = max(dp[j-2] + val[j], dp[j-1]);  //j-2肯定不能和ｊ-1匹配(理由同上)，只能和ｊ匹配，j-1也不能和j匹配
			}
			sum+=dp[m-1];  //加上这一组的最大人数
		}
	}
	return sum;
}