题解：dp[a[i]]=max(dp[a[i]-d]~dp[a[i]+d])。
感受：学会看数据啊，刚开始想的是贪心，发现可以不连续，看了数据，想了分块，线段树。。。最后发现可以dp。刚好一个小时
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn = 100005; 8 9 int T, n, d; 10 int a[maxn], dp[maxn]; 11 12 int main() 13 { 14 cin >> T; 15 while (T--) { 16 cin >> n >> d; 17 memset(dp, 0, sizeof(dp)); 18 for (int i = 1; i <= n; i++) cin >> a[i]; 19 dp[a[1]] = 1; 20 for (int i = 2; i <= n; i++) { 21 int start = max(1, a[i] - d); 22 int end = min(100000, a[i] + d); 23 int ans = 0; 24 for (int j = start; j <= end; j++) { 25 ans = max(ans, dp[j]); 26 } 27 dp[a[i]] = ans + 1; 28 } 29 int ans = 0; 30 for (int i = 1; i <= 100000; i++) ans = max(ans, dp[i]); 31 cout << ans << endl; 32 } 33 return 0; 34 }