zoj 2527 - Series
来源：程序员人生 发布时间：2014-10-08 08:44:20 阅读次数：2361次
题目：计算最长的等差数列长度。
分析：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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
