题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;

    int num[n+10];
    for(int i = 1;i <= n ;i ++)cin >> num[i];
    num[0] = 0;
    sort(num,num + n + 1);

    int dp[n + 10][k + 10];
    memset(dp,0,sizeof(dp));

    int tt = 1;//左指针，指向比第i个数小5之内的数的位置，初始为1;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= min(i,k);j ++)
        {
            while(num[tt] + 5 < num[i])tt ++;
            dp[i][j] = max(dp[i-1][j],dp[tt-1][j-1] + i - tt + 1);//[i-1][j]即放弃以i为右端点，[tt-1][j-1]即以i为右端点
        }
    cout << dp[n][k];
    return 0;
}