首页 > 其他 > 详细

E. K Balanced Teams

时间:2019-03-09 15:50:53      阅读:212      评论:0      收藏:0      [点我收藏+]

类比背包问题,为每个学生附加一个权重$pos[i]$,意思是选择该学生后,之后可以选择$p[i]~p[i]+5$的学生。

转换公式:
$$d[i][j]=max(d[i+1][q],d[i+pos][i]-pos[i])$$

#include<bits/stdc++.h>
using namespace std;
int p[5005],d[5005][5005],pos[5005];
int n;
int f(int i,int q){
    if(q==0||i>n)return 0;
    int& ans=d[i][q];
    if(ans) return ans;
    return ans=max(f(i+1,q),f(i+pos[i],q-1)+pos[i]);
}
int main(){
    int m;
    cin>>n>>m;
    for(int i{1};i<=n;i++) cin>>p[i];
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++) pos[i]=upper_bound(p+1,p+n+1,p[i]+5)-p-i;
    cout<<f(1,m)<<endl;
return 0;
}

E. K Balanced Teams

原文:https://www.cnblogs.com/boating/p/10500683.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!