Codeforces Round #156 (Div. 2) C. Almost Arithmetical Progression dp

72 阅读 0 评论 48 点赞

我是靠谱客的博主精明钢笔，最近开发中收集的这篇文章主要介绍Codeforces Round #156 (Div. 2) C. Almost Arithmetical Progression dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:

a1 = p, where p is some integer;
ai = ai - 1 + ( - 1)i + 1·q (i > 1), where q is some integer.
Right now Gena has a piece of paper with sequence b, consisting of n integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

Sequence s1, s2, …, sk is a subsequence of sequence b1, b2, …, bn, if there is such increasing sequence of indexes i1, i2, …, ik (1 ≤ i1 < i2 < … < ik ≤ n), that bij = sj. In other words, sequence s can be obtained from b by crossing out some elements.

Input
The first line contains integer n (1 ≤ n ≤ 4000). The next line contains n integers b1, b2, …, bn (1 ≤ bi ≤ 106).

Output
Print a single integer — the length of the required longest subsequence.

Examples
inputCopy
2
3 5
outputCopy
2
inputCopy
4
10 20 10 30
outputCopy
3
Note
In the first test the sequence actually is the suitable subsequence.

In the second test the following subsequence fits: 10, 20, 10.

题意很明确：
看满足p,p-q,p,p-q……的最长子序列

考虑dp[ i ][ j ]:
表示最后最后两个数字为 ai,aj 时的序列长度：
那么 dp[ i ][ j ]=dp[ last ][ i ]+1;
last 表示离 i 最近且 a[ last ]= a[ j ] 的位置

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<vector>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long int ull;
#define eps 1e-5
typedef pair<int,int> pii;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b){
if(b%2)ans=ans*a%mod;
b=b/2;
a=a*a%mod;
}
return ans;
}
int a[maxn];
int dp[5004][5004];
//dp[i][j]=dp[last][i]+1;
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
int i,j;
for(i=1;i<=n;i++)cin>>a[i];
int maxx=0;
dp[0][0]=0;
int last=0;
for(j=1;j<=n;j++){
for(i=0,last=0;i<j;i++){
dp[i][j]=dp[last][i]+1;
if(a[i]==a[j]){
last=i;
}
maxx=max(maxx,dp[i][j]);
}
}
cout<<maxx<<endl;
}