题目出处： http://acm.hdu.edu.cn/showproblem.php?pid=5064
题意： 给定n个数，求满足以下两个条件的子序列的最大长度：
（1）C 1 <C 2 <C 3 <......<C t ;
（2）C 2 -C 1 <C 3 -C 2 <......<C t -C t-1 .
分析： 解结构一定为为N 1 ，N 1 ，N 1 ，......，N 1 ，N 2 ，N 3 ，......，N t
设dp[i][j]表示以num[i], num[j]结尾的有效序列的长度，则有
dp[i][j] = max(dp[k][i]+ 1) ,,,,,,,k<=i且num[i]-num[k]<=num[j]-num[i]
剪枝一：
考虑非递减序列 num[s]，num[k]，num[i]，num[j] ，num[e]，
容易得到 dp[s][i]<=dp[s][i] （例如1,2,3） 即右端点固定 左端点越远越小，
同时因为序列从小到大排列，因此 左端点越远num[i]-num[k]越大，
所以，对于算某一特定的dp[i][j]时num[j]-num[i]是一个定值从k=i开始递减遍历dp[k][i]+ 1 取最大值，待条件不满足时跳出循环。
剪枝二：
因为 若num[i]-num[k]<=num[j]-num[i]成立 则num[i]-num[k]<=num[j+1]-num[i]必成立，
即 dp[i][j]<=dp[i][j+1] （例如 1(num[k])，4(num[i])，5(num[j])，8(num[j+1])）
即 左端点固定 小区间能取到的序列 大区间一定可以取到，
所以，每次计算新的dp[i][j]时k只要在上次的基础上继续向左遍历dp[k][i]+ 1，取最大值即可。
源代码：
1
#include<cstdio>
2
#include<iostream>
3
#include<map>
4
using
namespace
std;
5
int
n,M,num[
3000
],cnt[
3000
],size,dp[
3000
][
3000
];
6
7
int
maxVal(
int
a,
int
b){
return
a>b?
a:b;}
8
9
int
main()
10
{
11
int
t;
12
scanf(
"
%d
"
,&
t);
13
while
(t--
)
14
{
15
scanf(
"
%d%d
"
,&n,&
M);
16
int
i,j,k;
17
size =
0
;
//
序列中有size个不同的数
18
map<
int
,
int
>
mp;
19
map<
int
,
int
>
::iterator it;
20
//
记录序列中某个数i出现了几次,
21
for
(i=
0
;i<n;i++
)
22
{
23
int
a;
24
scanf(
"
%d
"
,&
a);
25
mp[a]++
;
26
}
27
//
用map是可以默认取数据时从小到大
28
//
PS：网络上不用map用数组预先处理的执行时间约600MS，用map约200MS
29
for
(it=mp.begin(); it!=mp.end();it++
)
30
{
31
num[size] = it->
first;
32
cnt[size] = it->
second;
33
size++
;
34
}
35
36
int
res =
1
;
37
for
(i=
0
;i<size;i++
)
38
{
39
dp[i][i] =
cnt[i];
40
res =
maxVal(res, dp[i][i]);
41
k=
i;
42
int
temp = -
1
;
43
for
(j=i+
1
;j<size;j++
)
44
{
45
for
(;k>=
0
;k--
)
46
{
47
if
(num[i]-num[k]<=num[j]-
num[i])
48
{
49
temp = maxVal(dp[k][i] +
1
,temp);
50
}
51
else
52
{
53
break
;
54
}
55
}
56
dp[i][j] =
temp;
57
res =
maxVal(res, dp[i][j]);
58
}
59
}
60
printf(
"
%d\n
"
,res);
61
62
}
63
return
0
;
64
}
