Codeforces 1133E - K Balanced Teams - [DP]
2024-10-02 04:19:47
题目链接:https://codeforces.com/contest/1133/problem/C
题意:
给出 $n$ 个数,选取其中若干个数分别组成 $k$ 组,要求每组内最大值与最小值的差值不超过5,求 $k$ 组合起来最多可以放多少个数。
题解:
将 $a[1 \sim n]$ 从小到大排序,排序后每个组必定可以视为数组 $a$ 上一段连续区间,
$f[i][j]$ 表示到第 $i$ 个数为止,前面组成 $j$ 组,最多可以包含多少个数。
那么,考虑第 $i$ 个数选取与否,如果不选,那么 $f[i][j]=f[i-1][j]$;
如果选,那么必然是第 $i$ 个数所在组人数加上前面那些组人数,假设 $p$ 表示距离 $a[i]$ 左侧最远的那个位置(满足 $a[i]-a[p] \le 5$),$f[i][j]=(i-p+1)+f[p-1][j-1]$。
AC代码:
用lower_bound找 $p$,时间复杂度 $O(n \log n + nk)$。
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,k,ans;
int a[maxn];
int f[maxn][maxn];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>k;
for(int i=;i<=n;i++) cin>>a[i];
sort(a+,a+n+); ans=f[][]=;
for(int i=;i<=n;i++)
{
int p=lower_bound(a+,a+i+,a[i]-)-a;
for(int j=;j<=min(k,i);j++)
{
f[i][j]=max(f[i-][j],(i-p+)+f[p-][j-]);
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
}
线性维护 $p$,时间复杂度 $O(nk)$。
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,k,ans;
int a[maxn];
int f[maxn][maxn];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>k;
for(int i=;i<=n;i++) cin>>a[i];
sort(a+,a+n+); ans=f[][]=;
int p=;
for(int i=;i<=n;i++)
{
while(p<i && a[i]-a[p]>) p++;
for(int j=;j<=min(k,i);j++)
{
f[i][j]=max(f[i-][j],(i-p+)+f[p-][j-]);
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
}
最新文章
- 每天一个设计模式-3 适配器模式(Adapteer)
- 【BZOJ-2325】道馆之战 树链剖分 + 线段树
- php查看网页源代码的方法
- PHP常用的一些正则表达式
- css3之过渡
- (转)为什么大公司青睐Java
- sqlite3内存不断增加的原因
- Check the difficulty of problems(POJ 2151)
- C#中反射的使用(How to use reflect in CSharp)(3)Emit的使用
- Fedora安装VirtualBox时出现错误Kernel driver not installed (rc=-1908)的解决办法
- Python第一天-----简单登录验证
- ios中的关键词retain release
- JS函数-我调用自己试试看
- AC自动机模板1(【洛谷3808】)
- MongoDB 自动增长
- 求数组中两数之和等于target的两个数的下标
- Tomcat 目录结构以及基本配置
- 论Object.keys(), Object.getOwnPropertyNames(), for in, Object.getOwnPropertySymbol()区别
- error TS2304: Cannot find name &#39;Promise&#39; &;&; TS2307: Cannot find module &#39;**&#39;
- video 播放本地视屏