小明刚刚入职淘宝，老大给他交代了一个简单的任务，实现一个简易的商品推荐系统。
这个商品推荐系统的需求如下：
一共有 n 件商品可以被推荐，他们的编号分别为 1 到 n。每件商品都有一个价格，编号为 i 的商品价格为 pi 元。现在需要给用户推荐尽可能多的商品，但是要保证按照编号上升的顺序给用户依次推荐商品，并且，相邻商品的价格之差的绝对值不能超过 d。注意，第一个推荐的商品价格没有限制。
输入格式
第一行输入一个整数 T，表示测试数据组数。
接下来依次输入 T 组数据，每组数据按照下面的格式输入：
第一行输入两个整数 n 和 d，意义如题目描述所示。
接下来一行输入 n 个整数，第 i 个整数表示 pi。
保证 $1<T≤50$, $1≤n≤30000$, $0≤d≤100$, $1≤pi≤10^5$。
保证 $∑n≤6∗10^5$。
输出格式
对于每组数据，输出一行一个整数，表示最多能推荐的商品个数。
题目分析
诶，思路大概被最近做的题目带的有点偏……
看到的第一眼是二分，然后果断叉掉了……
然后就开始想带记忆化的DFS，不过捣鼓了半天发现是会TLE的……
赛时dp一直没怎么理解，直到赛后才意识到好水好水的dp题目啊……
大概是dp姿势不太好吧……
这个是带记忆化的DFS：
#include<bits/stdc++.h>
const int maxn = ; int tt,n,m,ans;
int a[maxn],anss[maxn];
bool vis[maxn]; int dfs(int now)
{
if (vis[now]) return anss[now];
int tt = now, cnt = ;
for (;;)
{
tt++;
while (abs(a[tt]-a[now])>m) tt++;
if (tt <= n) cnt = std::max(dfs(tt), cnt);
else break;
}
vis[now] = ;
return anss[now]=cnt+;
}
int main()
{
scanf("%d",&tt);
while (tt--)
{
ans = ;
scanf("%d%d",&n,&m);
memset(vis, , sizeof vis);
memset(anss, , sizeof anss);
for (int i=; i<=n; i++) scanf("%d",&a[i]),anss[i] = ;
for (int i=; i<=n; i++)
if (!vis[i])
ans = std::max(ans, dfs(i));
printf("%d\n",ans);
}
return ;
}
这个是dp：
#include<bits/stdc++.h>
const int maxn = ; int tt,x,n,m,ans;
int f[maxn]; int main()
{
scanf("%d",&tt);
while (tt--)
{
ans = ;
scanf("%d%d",&n,&m);
memset(f, , sizeof f);
for (int i=; i<=n; i++)
{
scanf("%d",&x);
int w = f[x]+;
for (int j=std::max(, x-m); j<=std::min(maxn-, x+m); j++) //不要局限于数据形式，把dp对象转移成权值
f[j] = std::max(f[j], w);
}
for (int i=; i<maxn; i++)
ans = std::max(ans, f[i]);
printf("%d\n",ans);
}
return ;
}
其中注意到权值较小，我们用$f[j]$表示权值等于$j$时的最大答案值，最后再扫一遍就好了。
关键在于这里的输入天然有序，因此$f[j]$表示$1~i-1$之中权值为$j$的答案数，也就是说这里是把n维的dp优化到了1维。
END