E. K Balanced Teams

类比背包问题，为每个学生附加一个权重$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

最新文章

热门文章