https://codeforces.com/contest/1133/problem/E
题意
给你 n 个数 (n<=5000), 你需要对其挑选并进行分组, 总组数不能超过 k(k<=5000), 每组数字差距不超过 5, 问最多能挑出多少数字
题解
先排序, 在进行 dp, 定义 dp[i][j] 为前 i 个数分成 j 组的最大值
两个转移方向
不选 dp[i-1][j] -> dp[i][j]
和前面的分组 dp[lt[i]-1][j-1] -> dp[i][j]
怎么确定 i 前面的哪个点是最大的?
选择能和 i 分到一组的最前面的数
因为选择最前面的数可以降低前一组的上限
用双指针 or 单调队列处理
双指针板子
- for(l=r=n;l>=1;){
- if(l<=r){
- if(a[r]-a[l]<=5)
- lt[r]=l--;
- else lt[--r]=++l; //l++ 十分重要, 因为可能新的 l 和新的 r 不合适, 这样就 r 就会继续向左移动, 原来的 r 并没有找到和他合适的 l
- }else lt[r]=--l;
- }
代码
- include<bits/stdc++.h>
- define M 5005
- using namespace std;
- long long a[M],n,k,i,j,p,ans=0,dp[M][M],lt[M],l,r;
- int main(){
- cin>>n>>k;
- for(i=1;i<=n;i++){
- scanf("%lld",&a[i]);
- lt[i]=i;
- }
- sort(a+1,a+n+1);
- for(l=r=n;l>=1;){
- if(l<=r){
- if(a[r]-a[l]<=5)
- lt[r]=l--;
- else lt[--r]=++l;
- }else lt[r]=--l;
- }
- for(i=1;i<=n;i++){
- for(j=1;j<=min(k,n);j++){
- p=lt[i];
- dp[i][j]=max(dp[i-1][j],dp[p-1][j-1]+i-p+1);
- ans=max(dp[i][j],ans);
- }
- }
- cout<<ans;
- }
- ```
来源: http://www.bubuko.com/infodetail-2981811.html