拿到手第一想法就是算一下每个人可以和他分一起的，然后贪心。很显然在1s内被自己hack。所以贪心不行优先考虑dp。看到n和k的范围明显是个O(n^2)的dp。
由于我们不考虑顺序，按常规把水平排个序。
我的最初想法：
设f[i][j]：前i个人分了j组的最大和。
1.h[i]-h[lst]<=5 我们可以把他分到j-1组也可以分到第j组
2.h[i]-h[lst]>5 只能把i分到第j组
但我们遇到一个问题，就是我们不清楚第j-1组的开头到底是哪个。所以我又重新思考了一下：
f[i][j]=Max(f[i-1][j],f[lst][j-1]+i-lst);
表示第i个人是分到第j组还是和lst+1~i-1的数一起分到第j-1组。
此处的lst是最晚的不可以和i分到一组的，或者说最早可以和i分到一组的前一个。这样可以保证答案最大。
然后由于a[i]是升序的，这次的lst直接从上次的往后移就行。
1 #include<stdio.h> 2 #include<algorithm> 3 #define it register int 4 #define il inline 5 using namespace std; 6 const int N=5005; 7 int n,k,a[N],ans,f[N][N]; 8 il void fr(int &num){ 9 num=0;char c=getchar();int p=1; 10 while(c<‘0‘||c>‘9‘) c==‘-‘?p=-1,c=getchar():c=getchar(); 11 while(c>=‘0‘&&c<=‘9‘) num=num*10+c-‘0‘,c=getchar(); 12 num*=p; 13 } 14 il int Max(it p,it q){ 15 return p>q?p:q; 16 } 17 int main(){ 18 fr(n),fr(k); 19 for(it i=1;i<=n;++i) fr(a[i]); 20 sort(a+1,a+1+n); 21 for(it i=1,lst=0;i<=n;++i){ 22 while(a[i]-a[lst+1]>5) ++lst; 23 for(it j=1;j<=k;++j) f[i][j]=Max(f[i-1][j],f[lst][j-1]+i-lst); 24 } 25 for(it i=1;i<=k;++i) ans=Max(ans,f[n][i]); 26 printf("%d",ans); 27 return 0; 28 }
原文：https://www.cnblogs.com/Kylin-xy/p/11698461.html
