zoj 2527 - Series
來源：程序員人生 發布時間：2014-10-08 08:44:20 閱讀次數：2505次
題目：計算最長的等差數列長度。
分析：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
