Codeforces 156C Almost Arithmetical Progression

69 阅读 0 评论 46 点赞

我是靠谱客的博主孝顺老鼠，最近开发中收集的这篇文章主要介绍Codeforces 156C Almost Arithmetical Progression，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给你一个数列，问你其中最长波形子序列（a,b,a,b,a,b这样）最长为多少.

解题思路：找到pre[i][j]，就是在 i 前面且等于 a[i] 且离 i最近的值， dp[i][j] = dp[j][pre[j][i]] + 1;

解题代码：

 1 // File Name: 255c.cpp
 2 // Author: darkdream
 3 // Created Time: 2015年03月10日 星期二 16时26分53秒
 4
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 #define maxn 4005
26 using namespace std;
27 int dp[maxn][maxn];
28 int pre[maxn][maxn];
29 int a[maxn];
30 int hs[1000005];
31 int main(){
32
int n ;
33
scanf("%d",&n);
34
for(int i = 1;i <= n;i ++)
35 
{
36
scanf("%d",&a[i]);
37 
}
38
for(int i = 1;i <= n;i ++)
39 
{
40
for(int j = i+1 ;j <= n
;j ++)
41 
{
42
pre[i][j] = hs[a[j]];
43 
}
44
hs[a[i]] = i ;
45 
}
46
memset(dp,0,sizeof(dp));
47
int ans = 1 ;
48
for(int i = 1;i<=n;i ++)
49 
{
50
dp[i][0] = 1;
51
for(int j = 1;j < i;j ++)
52 
{
53
dp[i][j] = dp[j][pre[j][i]] + 1;
54
ans = max(ans,dp[i][j]);
55 
}
56 
}
57
printf("%dn",ans);
58 return 0;
59 }