【Codeforces Round #544 (Div. 3) E. K Balanced Teams】DP

　

dp

---

E. K Balanced Teams

题意

给你n个数，分成k组，要求每组内最大值与最小值的差值不超过5。求k组最多可以放多少个数。

$1\le n,k\le 5000$1≤n,k≤5000

做法

首先对数组排序，我们可以预处理每个数最多可以向左扩展的长度。

之后我们用$dp\left[i\right]\left[j\right]$dp[i][j]表示前i个数分为j组最多可以放多少个数。

对于每个i，一定是从之前预处理的位置转移过来，因为一段应该放尽量多的值。

我们设位置$i$i能够扩展的最左位置为$l\left[i\right]$l[i]。那么转移方程为:

$dp\left[i\right]\left[j\right]=max\left(dp\right[i-1\left]\right[j],dp[i\left]\right[j-1],dp[l\left[i\right]-1\left]\right[j-1]+i-l[i]+1)$dp[i][j]=max(dp[i−1][j],dp[i][j−1],dp[l[i]−1][j−1]+i−l[i]+1)

最后$dp\left[n\right]\left[k\right]$dp[n][k]便是答案。

代码

#include<stdio.h>
#include<iOStream>
#include<algorithm>
using namespace std;
const int maxn = 5005;
int a[maxn],l[maxn];
int dp[maxn][maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    dp[0][0]=0;
    for(int i=1;i<=n;i++) l[i]=lower_bound(a+1,a+1+n,a[i]-5)-a;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            dp[i][j]=max(dp[i][j],dp[l[i]-1][j-1]+i-l[i]+1);
        }
    }
    printf("%d\n",dp[n][k]);
    return 0;
}

相关阅读

蓝牙（三）a2dp连接

以下内容都是基于android6.0的基础上讲的，相对于android4.4架构有了很大改动。先借用一下图用一下。 上图描述的是蓝牙协议栈，通过

区间dp入门

一.什么是区间dp?顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个

LabeledPoint

Labeled point A labeled point is a local vector, either dense or sparse, associated with a label/response. In MLlib, la

HDFS加密存储（HDP、Ranger、Ranger KMS实现）

HDFS加密存储，在CSDN上可以看到很多的前辈整理的博客，但是按照https://blog.csdn.net/linlinv3/article/details/44963429所介绍的

电脑显卡4种接口类型：VGA、DVI、HDMI、DP

电脑显卡全称显示接口卡（Video card，Graphics card），又称为显示适配器（Video adapter），显示器配置卡简称为显卡，是个人电脑最基本组成部分