【hash+DP】51Nod 1055 最长等差数列

题面在这里

因为所求数列只跟给的值有关,先排序再说

定义\(f_{i,j}\)表示等差数列最后一项为\(a_j\),倒数第二项为\(a_i\)

\(f_{i,j}=f_{k,i}+1\)

然后这个\(a_k\)是可以算出来的,直接用MAP记录每个值最后出现的位置就好了

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

const int maxn=10005;
int n,a[maxn];
short f[maxn][maxn];
map<int,int> M;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n); int ans=2;
for (int i=1;i<=n;i++){
int tem=0;
for (int j=i+1;j<=n;j++)
if (2*a[i]-a[j]>0&&(tem=M[2*a[i]-a[j]])) f[i][j]=f[tem][i]+1,ans=max(ans,(int)f[i][j]);
else f[i][j]=2;
M[a[i]]=i;
}
printf("%d",ans);
return 0;
}