类比背包问题, 为每个学生附加一个权重 $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;
- }
来源: http://www.bubuko.com/infodetail-2981542.html