51nod1055：最长等差数列（dp）-白红宇

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

阅读量：6086 次

发布时间：2019-06-20

本文共 895 字，大约阅读时间需要 2 分钟。

基准时间限制：2 秒空间限制：262144 KB 分值: 80

关注

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示例

1013568910121314

Output示例

思路：动态规划，两边拓展，O(n^2)，从这里学习的：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std ;int const maxn = 10005;int a[maxn];short int dp[maxn][maxn];    //dp[i][j]表示的是以i和j为前两个元素的AP最长值,i
         
          = 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 ;}