做了两天题后有点头昏脑胀，上星期连着熬夜看联盟杯的后遗症不失时机地蹦出来张牙舞爪。也罢，这个礼拜要好好休息，不看冠军杯了。 （其实上个赛季也都是看Bt录播，人懒没药医 =.= ）

一道简单的DP。难点在于原来的算法时间复杂度O(N^3)，N=1000。

题目描述相当简单，给定一个数组，求其中最长的等差数列的长度。

首先考虑一维规划。显然不行，一个等差数列不能用一个数字进行定义。转而考虑二维。当数列的差不大时，可以考虑用F(i,d)表示当前一个数a[i]下等差为d的数列长度。可是这个数列给出了1e10的范围……

继续转进。F(i,j)表示数列的最后一个数是a[i],倒数第二个是a[j]。这样就保存了等差，也可以求得倒数第三个数，前提是找得到。只要在数组里找到它的位置k，就可以继续方程式：F(i,j) = F(j,k) + 1。

但是这样一来无疑要遍历整个数组，使O上升到N^3，这太慢了。为此先对整个数组排序，去除重复的数字，然后在有序的数组里可以用二分搜索k。O(N^2*log(N))，完全满足时间要求。

#include <cstdio>
#include <string>
#include <cstdlib>

int b[1001][1001], a[1001], N, ans;

int cmp ( const void *a, const void *b )
{
    return *( int * ) a > *( int * ) b;
}

int init ();
int b_search ( int, int, int );
void dp ();

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    while ( init () )
    {
        dp ();
        printf ( "%d\n", ans );
    }
    return 0;
}

int init ()
{
    if ( scanf ( "%d", &N ) == EOF )
    {
        return 0;
    }
    int i;
    for ( i = 0; i < N; i ++ )
    {
        scanf ( "%d", &a[i] );
    }
    ans = 0;
    qsort ( a, N, sizeof ( a[0] ), cmp );
    int pre = 1000000001, l = 0, t;
    for ( i = 0; i < N; i ++ )
    {
        if ( a[i] != pre )
        {
            a[l ++] = a[i];
            if ( ans < t )
            {
                ans = t;
            }
            t = 1;
        }
        else
        {
            t ++;
        }
        pre = a[i];
    }
    if ( ans < t )
    {
        ans = t;
    }
    return N = l;
}

void dp ()
{
    int i, j;
    for ( i = 0; i < N; i ++ )
    {
        for ( j = i - 1; j >= 0; j -- )
        {
            int l = 2 * a[j] - a[i];
            int k = b_search ( l, 0, j - 1 );
            if ( k == -1 )
            {
                b[i][j] = 2;
            }
            else
            {
                b[i][j] = b[j][k] + 1;
            }
            if ( ans < b[i][j] )
            {
                ans = b[i][j];
            }
        }
    }
}

int b_search ( int x, int l, int r )
{
    if ( x <a[l] || x> a[r] )
    {
        return -1;
    }
    int m;
    while ( l <= r )
    {
        m = ( l + r ) >> 1;
        if ( a[m] == x )
        {
            return m;
        }
        if ( a[m] > x )
        {
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return -1;
}

评论