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

题面在这里

​

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

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

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

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

​

示例程序：

#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;
}