51nod 1055最长等差数列 dp

灰太狼 2022-08-20 12:27 129阅读 0赞

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。

因为没看清题目意思纠结了好久，题目说的是找出由这些数组成的最长的等差数列，而不需要这些数字的排列顺序和输入的一样，这样我们就可以排序之后在来考虑。因为之前一直觉得题意是等差数列的顺序应该和输入的数字的顺序一样。。。。。。

因为题目所给的数组的范围是10000，所以我们可以考虑n^2的算法来写。

刚开始想了好久不知道dp应该怎么弄，最后突然想到可以用dp\[i\]\[j\]其中的i，j代表的是AP最前面的两个元素，并且i<j，这样求解之后将最终的结果遍历一遍就可以找到答案。

我们可以想到，不管i,j的位置是什么，dp\[i\]\[j\]最小值为2，我们可以先初始化。

然后我们先固定j，向两边扩展i=j-1,k=j+1。当2\*a\[j\]==a\[i\]+a\[k\]的时候，说明a\[i\]，a\[j\]，a\[k\]可以组成AP，这时候dp\[i\]\[j\] = dp\[j\]\[k\]+1 .

具体看代码

#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 ;
    }