https://nanti.jisuanke.com/t/26984
2018 计蒜之道 初赛 第二场 A
小明刚刚入职淘宝，老大给他交代了一个简单的任务，实现一个简易的商品推荐系统。
这个商品推荐系统的需求如下
一共有 n 件商品可以被推荐，他们的编号分别为 1 到 n。每件商品都有一个价格，编号为 i 的商品价格为 p i 元。现在需要给用户推荐尽可能多的商品，但是要保证按照编号上升的顺序给用户依次推荐商品，并且，相邻商品的价格之差的绝对值不能超过 d。注意，第一个推荐的商品价格没有限制。
输入格式
第一行输入一个整数 T，表示测试数据组数。
接下来依次输入 T 组数据，每组数据按照下面的格式输入：
第一行输入两个整数 n 和 d，意义如题目描述所示。
接下来一行输入 n 个整数，第 i个整数表示 p i
输出格式
对于每组数据，输出一行一个整数，表示最多能推荐的商品个数。
样例输入
2
6 3
5 7 3 6 10 9
8 6
4 7 9 5 8 1 9 10
样例输出
4
7
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 5;
int dp[maxn], pri[maxn];
int main()
{
int t, n, d, x;
cin >> t;
while(t--)
{
memset(dp, 0, sizeof(dp));
scanf("%d%d",&n, &d);
for(int i = 1; i <= n; i++)
scanf("%d", &pri[i]);
int ans = -1;
for(int i = 1; i <= n; i++)
{
int v = pri[i];
dp[v]++;
for(int k = -d; k <= d; k++)
{
int pre = v + k;
if(pre >= 1 && pre < maxn && dp[pre] && pre != v)
{
dp[v] = max(dp[v], dp[pre]+1);
// printf("%d %d %d\n", v, pre, dp[v]);
}
}
ans = max(ans, dp[v]);
}
printf("%d\n", ans);
}
return 0;
} 标准dp。有待理解
代码转载自https://blog.csdn.net/qq_34374664/article/details/80304600