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

解题思路:   这道题要求找出最大同时在线但不能匹配对局的用户数，我用的思路是动态规划，因为每两个相邻为K的用户都可以匹配，如果直接暴力搜索会出现牵一动百的情况，下面我来说一下我的思路：

         数据存储方式： 一维数组，下标表示分数，值表示该分数的人数。

        首先，将在线用户按比分进行分组，这里我采用一维数组，下标表示比分，值表示该比分的人数，这样，我们就可以把比分相差为K的用户分为若干组【例：K 为2 时 比分为0 2 4 6 8 10... 的用户为1组，1 3 5 7 9 ...的用户为第二组，再例：K为3时： 0 3 6 9...为一组 1 4 7 10...为一组  2 5 8 11为一组（就和希尔排序的分组差不多，只不过我们这里只分一次） 】,这样分完组后，组内元素之间有影响，组与组之间没有影响。

        然后，我们会发现，对于每一组，每两个相邻的值只能取一个（因为每两个相邻的元素相差都为K），那么很显然我们要选合适的一个，那怎么才能选合适的呢，这里就要进行动态规划了哈哈

         我们这里用 Ai表示第i个人，用dp[i]表示前i个人中最多能得到多少人。对于第i个人只有两种情况，被选，不被选。

            被选时： dp[i] = dp[i-2] + Ai;  

            不被选：dp[i] = dp[i-1];       

              当我们走完某一个分组时，就会得到该分组内能同时在线的最大人数，把每一个分组的最大人数都加一起，就是我们想要的结果了。

注意事项:  当 K =0 时应该单独考虑，因为分不开组，而且只要分数相同的时候就不能同时在线，那么这样的话，我们就只需要遍历我们分组之前建立的数组，就可以得到答案；

         如果谁有更好的方法或者我写的有什么不对的地方，欢迎讨论和指教！~~

参考代码:     

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#define MAX 100001
int max(int a,int b){   //选最大的比较函数    
	return a>b?a:b;
}
int dp(int arr[],int n,int k,int maxsc){   //动态规划函数 
	int count = 0;   //结果  
	if(k==0){   //如果K==0  单独处理，每个分数的人只允许一个在线  
		int i;
		for(i=0;i<=maxsc;i++){ 
			if(arr[i])count++;
		}
	}
	else{   //其他情况 
		int i,dp[MAX];   //dp数组用来存储 第 i 个人时 最多能同时在线的人数  
		for(i=0;i<k;i++){   //分组  对每一进行遍历的循环  如果看不懂 参考希尔排序第一趟   
			int m = 0;
			int val[MAX],j;  
			for(j=i;j<=maxsc;j+=k){
				val[m++]=arr[j];  //把该分组的值放到val数组   
			}
			dp[0]=val[0];  //就一个人的时候  肯定可以  直接放里边 
			for(j=1;j<m;j++){
				if(j==1)dp[j]=max(dp[0],val[j]);  //第二个人的时候  只有两个人的时候  不会对其他结果造成影响，直接选较大的   
				else dp[j]=max(dp[j-2]+val[j],dp[j-1]);  //从第三个人开始 最大人数受前面影响，但之前的最大在线人数已经在dp数组里面了 
			}
			count += dp[m-1];  //把每一个分组的最大人数加到一起   
		} 
	}
	return count;
}
int main(){
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF){
		int arr[MAX];
		memset(arr,0,sizeof(arr));  //这里必须初始化  
		int i,scor,maxscor=0;
		for(i=0;i<n;i++){  //数组组织方式： 下标是分数  值是该分数的人数   
			scanf("%d",&scor);
			arr[scor]++; 
			if(maxscor<scor)maxscor=scor;
		}
		int res = dp(arr,n,k,maxscor);  //动态规划  
		printf("%d\n",res);  //结果 
	}
}