51nod1055 最长等差数列（区间dp，哈希，双指针）

本文主要是介绍51nod1055 最长等差数列（区间dp，哈希，双指针），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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。

输入
第1行：N，N为正整数的数量(3 <= N <= 10000)。
第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)
输出
最长等差数列的长度。
输入样例
10
1
3
5
6
8
9
10
12
13
14
输出样例
5

思路：
注意，这里子序列的等差数列是排序以后的，不需要按照原来的顺序。
定义$dp[i][j]$为等差数列中第一个数为$a[i]$第二个数为$a[j]$的数列长度。
那么当$2\ast a[j]=a[i]+a[k]$的时候，意味着k可以成为等差数列第三个数
那么有$dp[i][j]=max(dp[i][j],dp[k][j]+1)$

原来的写法是确定一个中心端点然后两端扩展（因为等差数列有$2\ast a[j]=a[i]+a[k]$这样的性质），这样实质是双指针。

但是我们也很容易想到，如果对于 $dp[i][j]$这个状态（以$a[i]$为第一个数，$a[j]$为第二个数，只要找到一个$k$使得$2\ast a[j]=a[i]+a[k]$，则有 $dp[k][i]=max(dp[k][i],dp[i][j]+1)$，这个过程直接n^2写，关键就是找$k$的过程，我们要做到$o(1)$（或者常数尽量小），map肯定是不行的，这个过程可以用hash维护（但是用哈希表T了。。。）。

双指针AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int a[10005];
short int dp[10001][10001];short int Max(short int x,short int y) {return x > y ? x : y;
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);dp[i][i] = 1;for(int j = i + 1;j <= n;j++) {dp[i][j] = 2;}}sort(a + 1,a + 1 + n);short int ans = 2;for(int j = n - 1;j >= 2;j--) {int i = j - 1,k = j + 1;while(i >= 1 && k <= n) {if(a[j] * 2 == a[i] + a[k]) {dp[i][j] = Max(dp[i][j],dp[j][k] + 1);ans = Max(ans,dp[i][j]);i--;k++;}else if(a[i] + a[k] > a[j] * 2) i--;else k++;}}printf("%hd\n",ans);return 0;
}

哈希TLE代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <string>
#include <vector>
#include <map>using namespace std;typedef unsigned long long ull;
typedef long long ll;const int maxn = 1e4 + 1;
const int mod1 = 998311; //哈希表头
const int mod2 = 708031;
int head[1000000],nex[1000000],pos[1000000],val[1000000],tot;
short int dp[maxn][maxn];
int a[maxn];void add(ull H,int V,int x) {pos[++tot] = x;nex[tot] = head[H];val[tot] = V;head[H] = tot;
}int Find(int x) {if(x <= 0) return -1;ull tmp = x;ull H = tmp * mod2 % mod1;for(int i = head[H];i;i = nex[i]) {int v = pos[i],w = val[i];if(w == x) return v;}return -1;
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}sort(a + 1,a + 1 + n);for(int i = 1;i <= n;i++) {ull tmp = a[i];ull H = tmp * mod2 % mod1;add(H,a[i],i);}for(int i = 1;i <= n;i++) {for(int j = i + 1;j <= n;j++) {dp[i][j] = 2;}}for(int i = n - 1;i >= 1;i--) {for(int j = n;j > i;j--) {int num = 2 * a[i] - a[j];int k = Find(num);if(k != -1) {if(dp[k][i] < dp[i][j] + 1) {dp[k][i] = dp[i][j] + 1;}}}}short int ans = 0;for(int i = 1;i <= n;i++) {for(int j = i + 1;j <= n;j++) {ans = max(ans,dp[i][j]);}}printf("%hd\n",ans);return 0;
}

这篇关于51nod1055 最长等差数列（区间dp，哈希，双指针）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---