【51nod1055】最长等差数列

  • 本文为博主原创，未经许可不得转载

好久没有做dp题了

这题的状态转移也是挺妙的

$f[i][j]$表示以数列第$i$项$a[i]$和第$j$项$a[j]$为前两项的最长等差数列的长度

那么考虑若$a[k]$可以作为等差数列的第三项那么$f[i][j]=f[j][k]+1$

这里应该满足$a[j]*2=a[i]+a[k]$

我们每次枚举$j$的值，由于单调性，可以用两个指针$i,k$扫过去，从后往前转移

这样可以做到$O(n^2)$的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 10005
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
typedef short int Int;
int n,a[MAXN];
Int ans,f[MAXN][MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
Int max(Int a,Int b){return a>b?a:b;}
Int min(Int a,Int b){return a<b?a:b;}
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)f[i][j]=2;
	for(int j=n;j>=1;--j){
		int i=j-1,k=j+1;
		while(i>0&&k<=n){
			if(a[i]+a[k]<2*a[j]) ++k;
			else if(a[i]+a[k]>2*a[j])  --i;
			else if(a[i]+a[k]==2*a[j]){
				cmax(f[i][j],f[j][k]+1);
				cmax(ans,f[i][j]);--i;++k;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

本文标题:【51nod1055】最长等差数列

文章作者:chty

发布时间:2018年02月28日 - 21时09分

最后更新:2018年03月02日 - 17时32分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,