蓝桥杯国赛 对局匹配(DP)
题目描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分,代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时,只会将积分差恰好是 K 的两名用户匹配在一起。如果两人分差小于或大于 KK,系统都不会将他们匹配。
现在小明知道这个网站总共有 N名用户,以及他们的积分分别是
小明想了解最多可能有多少名用户同时在线寻找对手,但是系统却一场对局都匹配不起来(任意两名用户积分差不等于 K)?
输入描述
输入描述
第一行包含两个个整数
第二行包含 NN 个整数
其中,
输出描述
输出一个整数,代表答案。
输入输出样例
示例
输入
10 0 1 4 2 8 5 7 1 4 2 8
输出
6
思路
这道题有点难,我也是参考了众多博客终于大概搞明白了,这道题简单来说就是一个动态规划的问题,这里是差值只要是k就不能同时选,所以会将差值为k的划分为一组,然后每一组进行动态规划就可以了
首先最简单的就是k=0的情况,对于k=0的情况来说,我们只需要得到不同积分的数就可以了
而对于k不为0的情况,需要详细分析
首先把n个元素按照分数相差为k1的用户分为一组,例如第一组就是{0,k,2k,3k…},第二组就是{1,k+1,2k+1…}等,这样每个组的用户不可能和其他组的用户匹配成功,因为他们之间的差不可能为k
其二目标就是在每一个分组里面选取尽量多的用户,这一部分我们就可以用动态规划来求解,选取尽可能多的人数。dp[i]表示前i个积分能获得的最大用户数(不能匹配的)
如果 j 不上线,则 j-k 是会上线,所以人数就是j-k的人数
如果 j 上线, 则不影响 j-2*k,所以j-2k可以上线,所以最后是j的人数j-2k的人数
最后就可以得到我们的动态规划的方程,最后进行求解
代码
n,k = map(int,input().split()) a = list(map(int,input().split())) maxa = max(a) from collections import Counter c = Counter(a) if k == 0: print(len(c)) else: # dp[i]表示前i个积分能获得的最大用户数(不能匹配的) dp = [0]*(maxa+1) ans = 0 for i in range(0,k): maxindex = 0 # 这里相当于分组,分为{k,2k,3k....} # 希望在每一分组中选择尽可能多的客户 for j in range(i,maxa+1,k): if j - 2*k >= 0: # 如果 j 不上线,则j-k上线 # 如果 j 上线, 则不影响j-2*k,所以j-2k可以上线 dp[j] = max(dp[j-2*k]+c[j],dp[j-k]) elif j - k >= 0: dp[j] = max(dp[j-k],c[j]) else: dp[j] = c[j] maxindex = j ans += dp[maxindex] print(ans)