马和人做人和牛做网站/广州疫情最新新增

小明刚刚入职淘宝，老大给他交代了一个简单的任务，实现一个简易的商品推荐系统。

这个商品推荐系统的需求如下：

一共有 nn 件商品可以被推荐，他们的编号分别为 11 到 nn。每件商品都有一个价格，编号为 ii 的商品价格为 p_ipi​ 元。现在需要给用户推荐尽可能多的商品，但是要保证按照编号上升的顺序给用户依次推荐商品，并且，相邻商品的价格之差的绝对值不能超过 dd。注意，第一个推荐的商品价格没有限制。

输入格式

第一行输入一个整数 TT，表示测试数据组数。

接下来依次输入 TT 组数据，每组数据按照下面的格式输入：

第一行输入两个整数 nn 和 dd，意义如题目描述所示。

接下来一行输入 nn 个整数，第 ii 个整数表示 p_ipi​。

保证 1 \lt T \le 501<T≤50, 1 \le n \le 300001≤n≤30000, 0 \le d \le 1000≤d≤100, 1 \le p_i \le 10^51≤pi​≤105。

保证 \sum n \le 6*10^5∑n≤6∗105。

输出格式

对于每组数据，输出一行一个整数，表示最多能推荐的商品个数。

样例输入

思路：首先联想的最长上升子序列的dp思路，dp[i]表示以i结尾的最多个数。但是复杂度n^2。

考虑进行优化，普通做法，都是往前找（1到i-1项里满足的最大值），但是d<100,而满足的必然在a[i]-d,a[i]+d之间，所以，每次找只要在这样的区间找就行了，所以利用hash的映射思想，Max[a[i]]=dp[i]，表示以a[i]结尾的最大值为dp[i]，那么递推时只要去Max里查就行了。

代码：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int n;
int a[maxn];
int dp[maxn];
int Max[maxn];
int getMax(int l,int r)
{int ans=0;for(int i=l;i<=r;i++){ans=max(ans,Max[i]);}return ans;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint T;cin>>T;while(T--){int d;scanf("%d%d",&n,&d);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}memset(dp,0,sizeof(dp));memset(Max,0,sizeof(Max));dp[1]=1;Max[a[1]]=1;for(int i=2;i<=n;i++){dp[i]=getMax(max(0,a[i]-d),min(a[i]+d,maxn))+1;Max[a[i]]=dp[i];//类似hash}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i]);}printf("%d\n",ans);}return 0;
}