问题描述

　　小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

　　小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。

　　现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, … AN。

　　小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？

输入格式

　　第一行包含两个个整数N和K。
　　第二行包含N个整数A1, A2, … AN。

　　对于30%的数据，1 <= N <= 10
　　对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000

输出格式

　　一个整数，代表答案。

样例输入

10 0
1 4 2 8 5 7 1 4 2 8

样例输出

6

思路分析

题目要求任意两名用户的积分差不等于k，那我们就把积分差为k的用户放在一个集合里判断，这样就把所有用户分为了k个集合，这样任意两个不同的集合中的任意两个元素的积分差都不等于k，所以题目也相对的变成了求每一个集合中积分差不等于k的最大人数，动态规划，我们假设前i-1个状态对应的最大人数已经求出来了，所以第i个状态就是max(dp[i-1],dp[i-2]+a[i])，即不取第i个和取第i个的最大值，当i==0||i==1时，特判一下，还有特判k==0的情况就AC了。
在进行dp的的时候，最好另开一个数组开存每一个集合，这样dp写起来很舒服。

AC代码

#include<iostream>
using namespace std;
int book[100005],a[100005],dp[100005];
int main()
{
    int i,j,n,k,t,x=0,ans=0;
    cin>>n>>k;
    for (i=0;i<n;i++)
    {
        cin>>t;
        book[t]++;
    }
    if (k==0)
    {
        for (i=0;i<100005;i++)
        {
            if (book[i]!=0)
            ans++;
        }
        cout<<ans;
        return 0;
    }
    else
    {
        for (i=0;i<k;i++)
        {
            x=0;
            for (j=i;j<100005;j+=k)
            a[x++]=book[j];
            for (j=0;j<x;j++)
            {
                if (j==0)
                dp[0]=a[0];
                else if (j==1)
                dp[1]=max(a[1],dp[0]);
                else
                dp[j]=max(dp[j-1],dp[j-2]+a[j]);
            }
            ans+=dp[x-1];
        }
    }
    cout<<ans;
}