题目链接：https://nanti.jisuanke.com/t/26984
淘宝的推荐系统
小明刚刚入职淘宝，老大给他交代了一个简单的任务，实现一个简易的商品推荐系统。这个商品推荐系统的需求如下：
一共有 nn 件商品可以被推荐，他们的编号分别为 1 到 n。每件商品都有一个价格，编号为 i 的商品价格为 pi元。现在需要给用户推荐尽可能多的商品，但是要保证按照编号上升的顺序给用户依次推荐商品，并且，相邻商品的价格之差的绝对值不能超过 dd。注意，第一个推荐的商品价格没有限制。
输入格式
第一行输入一个整数 T，表示测试数据组数。
接下来依次输入 T 组数据，每组数据按照下面的格式输入：
第一行输入两个整数 n 和 d，意义如题目描述所示。
接下来一行输入 n 个整数，第i 个整数表示 pi。
保证 1<T≤50, 1≤n≤30000, 0 ≤d≤100, 1≤pi≤1e5。
保证 ∑n≤6∗1e5。
输出格式
对于每组数据，输出一行一个整数，表示最多能推荐的商品个数。
样例输入
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 <cstring>
#include <algorithm>
using namespace std;
;
int n, d;
int a[maxn];
int Max[maxn]; //Max[i]表示最后一个推荐的商品价格为i的最大数量
int dp[maxn]; //dp[i]表示最后一个推荐的商品编号为i的最大数量
int getmax(int l, int r) {
;
for (int i = l; i <= r; i++) {
ans = max(ans, Max[i]);
}
return ans; //找到符合条件的,推荐商品数量最大的值
}
int main() {
int t;
cin >> t;
while (t--)
{
memset(Max, , sizeof(Max));
cin >> n >> d;
; i <= n; i++) cin >> a[i];
; i <= n; i++)
{
, a[i] - d), min(a[i] + d, )); //对于价格为a[i]的商品，能转移Max[a[i]]的区间只有[a[i]-d,a[i]+d],然后进行暴力枚举转移即可
dp[i] = num + ; //因为Max数组编号大于i的此时Max[a[i]]的值都为0(仍然为初始值)，所以能够保证按照编号上升的顺序给用户依次推荐商品
Max[a[i]] = max(Max[a[i]], dp[i]);
}
;
; i <= n; i++) res = max(res, dp[i]);
cout << res << "\n";
}
;
}
2018-05-13