题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5064
题目意思：给出n个数：a1, a2, ..., an，然后需要从中找出一个最长的序列 b1, b2, ..., bt。需要满足两个条件（1）b1≤b2≤…≤bt （2）b2−b1≤b3−b2≤⋯≤bt−bt−1。求出最大的 t 为多少。
遗留大半年的题目呀呀呀呀~~~~！！！首先非常感谢乌冬子大半年前的指点迷津，呕心沥血想了大半天举出个反例，以便指出我算法的错误。为了纪念这个伟大的人物（hoho n_n），我就以他给出的数据作为例子吧。
一开始我真的觉得那个M是多余的，其实不然，由于M最大为 222 （4194304，计算机算出来的，千真万确！）。 那么每个数都是不同的最长数列是这样的：1， 2，3，...，n 。等差数列，即（1+n)*n / 2 = 4194304 , 算出来的 n 大概为3000，这个暗示我们开的数组大小为3000就足够了。
先看这组数据，不难发现，最优解是选择 10 11 12 13 100.
1
7 148
1 1 10 11 12 13 100
首先需要从小到大排序，把重复的数去掉，这个可以参考官方题解。
设dp[i][j]表示以第 j 个数为结尾，它前一个数为第 i 个且满足题目两个条件的最大选择个数。
可以写出这样的状态转移方程，
dp[i][j] = max(dp[i][j], dp[k][i]+1)， k <= i < j && b[i]-b[k] <= b[j]-b[i]
dp[k][i] 表示在 i 之前，以第 k 个数结尾，能使得 b[i]-b[k] <= b[j]-b[i]，即相对单纯地以第 i 个数结尾，b[i]-b[k] 的差比 b[j]-b[i] 还要小或者相等。然后就更新 dp[i][j] 的值了。
至于复杂度从O(x^3) 到 O(x^2) 可以参考其他题解，因为。。。俺还是不太完全理解 T_T
代码中还有个小地方希望有识之士提点提点，不胜感激~~~
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
int a[maxn*maxn];
int cnt[maxn], dp[maxn][maxn]; int main()
{
#ifndef ONLINE_JUDGE
freopen("in1.txt", "r", stdin);
#endif // ONLINE_JUDGE int cas, cur, n, m;
while (scanf("%d", &cas) != EOF) {
while (cas--) {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
scanf("%d", a+i);
}
sort(a+, a++n); cnt[cur=] = ;
for (int i = ; i <= n; i++) {
if (a[i] == a[cur]) {
cnt[cur]++;
}
else {
a[++cur] = a[i];
cnt[cur] = ;
}
}
memset(dp, , sizeof(dp));
n = cur;
for (int i = ; i <= n; i++) {
dp[i][i] = cnt[i];
} int ans = ;
for (int i = ; i <= n; i++) {
int k = i;
int tmp = dp[i][i];
ans = max(tmp, ans); // 没了这个会wa，疑问？
for (int j = i+; j <= n; j++) {
for ( ; k >= && a[i]-a[k] <= a[j]-a[i]; k--) {
tmp = max(tmp, dp[k][i]+); }
dp[i][j]= tmp;
ans = max(ans, tmp);
}
}
printf("%d\n", ans);
}
}
return ;
}