【洛谷P3143】Diamond Collector

算是一道dp

首先,排序好每一个架子上都是一段区间,然后只需要统计每个点向左向右最长延伸的区间。

所以我们预处理出每个点以左、以右最大能延伸的长度(最多能选几个差值不超过k的)

然后枚举每个点作为断点,sum取max即可

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,k,a[N],sum_l[N],sum_r[N];
int read(){
int sum=;
char ch=getchar();
while (ch<''||ch>'')
ch=getchar();
while (ch>=''&&ch<=''){
sum=sum*+ch-'';
ch=getchar();
}
return sum;
}
int main(){
int ans=,j;
n=read();
k=read();
for (int i=;i<=n;i++)
a[i]=read();
sort(a+,a+n+);
sum_l[]=;j=;
for (int i=;i<=n;i++){
while (a[i]-a[j]>k) j++;
sum_l[i]=max(sum_l[i-],i-j+);
}
sum_r[n]=;j=n;
for (int i=n-;i>=;i--){
while (a[j]-a[i]>k) j--;
sum_r[i]=max(sum_r[i+],j-i+);
}
for (int i=;i<n;i++)
ans=max(ans,sum_l[i]+sum_r[i+]);
printf("%d",ans);
return ;
}
上一篇:[USACO16OPEN]钻石收藏家Diamond Collector


下一篇:BZOJ 4582: [Usaco2016 Open]Diamond Collector