题目链接:https://codeforces.com/contest/1133/problem/E

题解:很显然可以看出dp方程为dp[i][j]=min(dp[i1][j],dp[t][j1]+(it+1))dp[i][j] = \min (dp[i-1][j], dp[t][j-1] + (i - t + 1))
其中设ll为第一个a[l]a[i]5a[l] \geq a[i] - 5的下标。 其中t[l,i]t \in [l, i] 很显然这是个O(n3)O(n ^ 3)

那么应该如何优化呢。 我们可以发现 每次转移的时候,没有必要从[l,i][l, i]每个都去转移。 只需要从ll去转移。
原因:不妨我们设t[l,i]t \in [l, i]t>it > i 那么目前我们只需要考虑的是dp[l][j]+(il+1)dp[l][j] + (i - l + 1)dp[t][j]+(it+1)dp[t][j] + (i - t + 1) 的关系不妨考虑dp[t][j]dp[t][j] 假设此时取到的一个最优序列为SS, 那么对于dp[l][j]dp[l][j] 而言必然能取到一个序列SS' 使得SS<=(tl)S - S' <= (t - l)也就是说,SS这个最优序列在前ll中,必然是能被dp[l][j]dp[l][j] 所覆盖到的 那么此时再从dp[t][j]dp[t][j]转移是冗余的,只需要从ll转移,所以得证

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 5005 + 5;
int n,k;
int dp[N][N];
int a[N];
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        int t = lower_bound(a + 1, a + n + 1, a[i] - 5) - a;
        for(int l = 1; l <= k; l++) {
            dp[i][l] = max(dp[t - 1][l - 1] + (i - t + 1), dp[i][l]);
        }
        for(int l = 1; l <= k; l++) dp[i][l] = max(dp[i - 1][l], dp[i][l]);
    }
    int ans = 0;
    for(int i = 1; i <= k; i++) ans = max(dp[n][i], ans);
    cout << ans;
    return 0;
}