CF1133E K Balanced Teams(DP)

/*
排序之后每个点往前能选择的是一段区间, 所以我们实际上转移位置是确定的
然后f[i][j]表示到了i选了j段的最大贡献, 显然状态数是O(n^2)的, 转移是O(1)的 


*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long 
#define M 5050
#define mmp make_pair
using namespace std;
int read()
{
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
int a[M], f[M][M], n, k; 
int main()
{
    n = read(), k = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++)
    {
        int pl = i;
        while(pl > 1 && a[i] - a[pl - 1] <= 5) pl--;
        for(int j = 1; j <= k; j++)
        {
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i][j], f[pl - 1][j - 1] + i - pl + 1);
        }
    }
    int ans = 0;
    for(int i = 1; i <= k; i++) ans = max(ans, f[n][i]);
    cout << ans << "\n";
    
    
    
    return 0;
}
上一篇:多校冲刺 NOIP 20211106 模拟 (24)


下一篇:noip多校模拟30