51nod1055： 最长等差数列（dp）

1055 最长等差数列 基准时间限制：2 秒 空间限制：262144 KB 分值: 80  难度：5级算法题  收藏  关注 N个不同的正整数，找出由这些数组成的最长的等差数列。 例如：1 3 5 6 8 9 10 12 13 14 等差子数列包括(仅包括两项的不列举） 1 3 5 1 5 9 13 3 6 9 12 3 8 13 5 9 13 6 8 10 12 14 其中6 8 10 12 14最长，长度为5。 Input 第1行：N，N为正整数的数量(3 <= N <= 10000)。 第2 - N+1行：N个正整数。(2<= A[i] <= 10^9) Output 最长等差数列的长度。 Input示例 10 1 3 5 6 8 9 10 12 13 14 Output示例 5

思路：动态规划，两边拓展，O(n^2)，从这里学习的：http://blog.csdn.net/liuyanfeier/article/details/50760657

#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> using namespace std ; int const maxn = 10005; int a[maxn]; short int dp[maxn][maxn]; //dp[i][j]表示的是以i和j为前两个元素的AP最长值,i<j int main() { int n ,ans ; while(scanf("%d",&n)!=EOF) { for(int i = 0 ; i < n ; i++) { scanf("%d",&a[i]); } sort(a,a+n); for(int i = 0 ; i < n ; i++) { for(int j = i+1 ; j < n ; j++) { dp[i][j] = 2 ; //AP最小值为2 } } ans = 2 ; for(int j = n-2 ; j >= 1 ; j--) { int i = j-1 , k = j+1 ; while(i>=0 && k<=n-1) { if(a[i]+a[k]<2*a[j]) { k++; } else if(a[i]+a[k]>2*a[j]) { i--; } else { dp[i][j] = dp[j][k]+1 ; if(dp[i][j]>ans)ans=dp[i][j]; i--;k++; } } } printf("%d\n",ans); } return 0 ; }