题目出处：http://acm.hdu.edu.cn/showproblem.php?pid=5064
题意：给定n个数，求满足以下两个条件的子序列的最大长度：
（1）C1<C2<C3<......<Ct;
（2）C2-C1<C3-C2<......<Ct-Ct-1.
分析：解结构一定为为N1，N1，N1，......，N1，N2，N3，......，Nt
设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 }
原文：http://www.cnblogs.com/MickWoo/p/4025191.html