Codeforces Round #544 (Div. 3) E. K Balanced Teams（DP）
本文共 529 字，大约阅读时间需要 1 分钟。
题意：有n个学生，每个学生有ai值，要求把学生分成不超过k组，同时一组内学生的ai值最大不能超过5，求能组队的最大学生数。 思路：排序后，能组队的肯定是连续的数，dp【i】【j】代表前i个学生组成j个组的最大学生数，只要在第二层循环里找到满足条件的pos位置。 #includeusing namespace std;const int maxn=5e3+5;int n,k,ans=0,pos=1,dp[maxn][maxn],a[maxn];int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;++i) { while(a[i]-a[pos]>5&&pos<=i) pos++; for(int j=1;j<=k;++j) dp[i][j]=max(dp[i-1][j],dp[pos-1][j-1]+i-pos+1); } for(int i=1;i<=k;++i) ans=max(ans,dp[n][i]); printf("%d\n",ans);}
转载地址：http://brewz.baihongyu.com/
你可能感兴趣的文章
No compiler is provided in this environment. Perhaps you are running on a JRE rather than a JDK?
查看>>
no connection could be made because the target machine actively refused it.问题解决
查看>>
No Datastore Session bound to thread, and configuration does not allow creation of non-transactional
查看>>
No fallbackFactory instance of type class com.ruoyi---SpringCloud Alibaba_若依微服务框架改造---工作笔记005
查看>>
No Feign Client for loadBalancing defined. Did you forget to include spring-cloud-starter-loadbalanc
查看>>
No mapping found for HTTP request with URI [/...] in DispatcherServlet with name ...的解决方法
查看>>
No mapping found for HTTP request with URI [/logout.do] in DispatcherServlet with name 'springmvc'
查看>>
No module named 'crispy_forms'等使用pycharm开发
查看>>
No module named cv2
查看>>
No module named tensorboard.main在安装tensorboardX的时候遇到的问题
查看>>
No module named ‘MySQLdb‘错误解决No module named ‘MySQLdb‘错误解决
查看>>
No new migrations found. Your system is up-to-date.
查看>>
No qualifying bean of type XXX found for dependency XXX.
查看>>
No qualifying bean of type ‘com.netflix.discovery.AbstractDiscoveryClientOptionalArgs＜?＞‘ available
查看>>
No resource identifier found for attribute 'srcCompat' in package的解决办法
查看>>
no session found for current thread
查看>>
No toolchains found in the NDK toolchains folder for ABI with prefix: mips64el-linux-android
查看>>
NO.23 ZenTaoPHP目录结构
查看>>
no1
查看>>
NO32 网络层次及OSI7层模型--TCP三次握手四次断开--子网划分
查看>>