首页 > 其他 > 详细

51nod1055 最长等差数列

时间:2017-06-23 22:50:40      阅读:336      评论:0      收藏:0      [点我收藏+]

 

基准时间限制:2 秒 空间限制:262144 KB 分值: 80 
N个不同的正整数,找出由这些数组成的最长的等差数列。
 
 
例如:1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举)
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14
 
其中6 8 10 12 14最长,长度为5。
 
 
Input
第1行:N,N为正整数的数量(3 <= N <= 10000)。
第2 - N+1行:N个正整数。(2<= A[i] <= 10^9)
Output
最长等差数列的长度。
Input示例
10
1
3
5
6
8
9
10
12
13
14
Output示例
5

 

动态规划  线性DP

注意到是“由这些数组成的”等差序列,也就是原数列没有顺序限制

将数列从小到大排序,设$ f[i][j] $为 “末尾两项是$ a[j] $和$ a[i] $的等差数列”的最长长度。

这个状态设计挺巧妙的,既记录了位置信息,又记录了公差。

然后从$1$到$n$枚举$i$,再枚举$ j $和$ k $,当满足 $ a[j]-a[k] = a[i]-a[j] $时,可以由$ f[j][k] $转移到$ f[i][j] $

这样做是$ O(n^3) $的。

注意到数列已经排好序了,转移条件是 $ a[k]+a[i] == a[j] + a[j] $,其中蕴藏着神秘又美丽的单调性

所以可以枚举 j,用双指针维护i和k,这样复杂度就降到 $ O(n^2)$了

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 using namespace std;
 7 const int mxn=10002;
 8 int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}
11     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}
12     return x*f;
13 }
14 int n;
15 int a[mxn];
16 short f[mxn][mxn];
17 int main(){
18     int i,j;
19     n=read();
20     for(i=1;i<=n;i++){
21         a[i]=read();
22     }
23     sort(a+1,a+n+1);
24     int ans=2;
25     for(i=1;i<n;i++){
26         j=i-1;
27         for(int k=i+1;k<=n && j>0;k++){
28             while(j && a[k]+a[j]>a[i]+a[i])j--;
29             if(j && a[k]+a[j]==a[i]+a[i]){
30                 f[k][i]=(f[i][j]==0)?3:(f[i][j]+1);
31                 ans=max(ans,(int)f[k][i]);
32             }
33         }
34     }
35     printf("%d\n",ans);
36     return 0;
37 }

 

51nod1055 最长等差数列

原文:http://www.cnblogs.com/SilverNebula/p/7071765.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!