2755219 2008-02-19 18:56:56 Accepted 2527 C++ 00:00.07 4364K C.D. 做了两天题后有点头昏脑胀，上星期连着熬夜看联盟杯的后遗症不失时机地蹦出来张牙舞爪。也罢，这个礼拜要好好休息，不看冠军杯了。 （其实上个赛季也都是看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;}

评论