国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > zoj 2527 - Series

zoj 2527 - Series

来源:程序员人生   发布时间:2014-10-08 08:44:20 阅读次数:2352次

题目:计算最长的等差数列长度。

分析:dp,LIS类似物,二分。先排序,然后枚举前面的所有点作为前一个元素求公差即可。

            更新时,利用二分找到,距离当前位置最近的前第二元素,

            如果不存在,则直接更新为 2即可。 

说明:如果数据范围小的话,可在连续区间dp(O(L^2))。(2011-10-03 17:34)

#include <stdio.h> #include <stdlib.h> int D[ 1005 ]; int F[ 1005 ][ 1005 ]; int cmp( const void* a, const void* b ) { return *((int *)a) - *((int *)b); } int find( int h, int key ) { int m,l = 1; while ( l < h ) { m = (l+h)>>1; if ( D[ m ] <= key ) l = m+1; else h = m; } return h; } int main() { int n; while ( ~scanf("%d",&n) ) { for ( int i = 1 ; i <= n ; ++ i ) scanf("%d",&D[ i ]); qsort( &D[ 1 ], n, sizeof( int ), cmp ); for ( int i = 1 ; i <= n ; ++ i ) for ( int j = 1 ; j < i ; ++ j ) F[ i ][ j ] = 1; for ( int i = 2 ; i <= n ; ++ i ) for ( int j = 1 ; j < i ; ++ j ) { int d = D[ i ]-D[ j ]; int s = find( j, D[ j ]-d )-1; if ( s > 0 && D[ s ] == D[ j ]-d ) { if ( F[ i ][ j ] <= F[ j ][ s ] ) F[ i ][ j ] = F[ j ][ s ] + 1; }else if ( s <= 0 || F[ i ][ j ] < 2 ) F[ i ][ j ] = 2; } int Min = 1; for ( int i = 1 ; i <= n ; ++ i ) for ( int j = 1 ; j < i ; ++ j ) if ( Min < F[ i ][ j ] ) Min = F[ i ][ j ]; printf("%d ",Min); } return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生