P11187 配对序列
题目描述
一个序列 s1,…s2ks_1,\\ldots s_{2k}s1,…s2k 是配对的，当且仅当：
- 对于任意 1≤i≤k1\\le i \\le k1≤i≤k，s2i=s2i−1s_{2i}=s_{2i-1}s2i=s2i−1。
- 对于任意 1≤i<k1\\le i<k1≤i<k，s2i≠s2i+1s_{2i}\\ne s_{2i+1}s2i=s2i+1。
注意，配对的序列长度必然为偶数。
例如，3,3,5,5,2,23,3,5,5,2,23,3,5,5,2,2 是配对的，而 2,2,2,2,5,52,2,2,2,5,52,2,2,2,5,5（s2=s3s_2=s_3s2=s3 不满足第二条要求）或者 1,2,3,3,1,11,2,3,3,1,11,2,3,3,1,1（s1≠s2s_1\\ne s_2s1=s2 不满足第一条要求）都不是配对的。
给出一个数列 a1,…,ana_1,\\ldots, a_na1,…,an，求所有配对的子序列长度的最大值。
输入格式
输入的第一行有一个正整数 nnn，表示序列的长度。
第二行有 nnn 个正整数 a1,…,ana_1,\\ldots,a_na1,…,an，表示这个序列。
输出格式
输出一行一个自然数，表示最长的配对子序列长度。特别地，如果不存在非空的配对子序列，那么输出 000。
输入输出样例 #1
输入 #1
8
1 2 2 2 2 1 2 2
输出 #1
4
输入输出样例 #2
输入 #2
11
1 1 4 1 1 2 1000 2 5 5 4
输出 #2
6
输入输出样例 #3
输入 #3
参见 pairing3.in
输出 #3
参见 pairing3.out
输入输出样例 #4
输入 #4
参见 pairing4.in
输出 #4
参见 pairing4.out
说明/提示
【样例 1 解释】
取 1,1,2,21,1,2,21,1,2,2 这个子序列即可。
【样例 2 解释】
取 1,1,2,2,5,51,1,2,2,5,51,1,2,2,5,5 这个配对子序列即可。
【样例 3 解释】
该样例符合测试点 333 的限制。
【样例 4 解释】
该样例符合测试点 121212 的限制。
【数据范围】
对于全体数据，保证 2≤n≤5×1052\\le n\\le 5\\times 10^52≤n≤5×105，1≤ai≤5×1051\\le a_i\\le 5\\times 10^51≤ai≤5×105。
| 1∼21\\sim 21∼2 | 181818 | 5×1055\\times 10^55×105 | |
| 3∼53\\sim 53∼5 | 500500500 | 500500500 | |
| 6∼76\\sim 76∼7 | 500050005000 | 500050005000 | |
| 8∼98\\sim 98∼9 | 500050005000 | 5×1055\\times 10^55×105 | |
| 101010 | 5×1055\\times 10^55×105 | 5×1055\\times 10^55×105 | 每个数最多出现 111 次 |
| 111111 | 5×1055\\times 10^55×105 | 5×1055\\times 10^55×105 | ai≤ai+1a_i\\le a_{i+1}ai≤ai+1 恒成立 |
| 12∼1412\\sim 1412∼14 | 5×1055\\times 10^55×105 | 5×1055\\times 10^55×105 | 每个数最多出现 222 次 |
| 15∼2015\\sim 2015∼20 | 5×1055\\times 10^55×105 | 5×1055\\times 10^55×105 |
C++实现
#include <bits/stdc++.h>
using namespace std;
int a[500010], dp[500010][3];
unordered_map<int, int> f;
int mx1, my1, mx2, my2;
int main() {
int n;
cin >> n;
dp[0][1] = –1e9;
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[i][0] = max(dp[i – 1][0], dp[i – 1][2]);
dp[i][2] = max(dp[i][2], dp[f[a[i]]][1] + 1);
if (mx1 == a[i]) {
dp[i][1] = dp[my2][2] + 1;
} else {
dp[i][1] = dp[my1][2] + 1;
}
if (mx1 == a[i]) {
if (dp[my1][2] < dp[i][2]) {
my1 = i;
}
} else if (mx2 == a[i]) {
if (dp[my2][2] < dp[i][2]) {
my2 = i;
}
if (dp[my2][2] > dp[my1][2]) {
swap(my1, my2);
swap(mx1, mx2);
}
} else {
if (dp[i][2] > dp[my1][2]) {
mx2 = mx1;
my2 = my1;
mx1 = a[i];
my1 = i;
} else if (dp[i][2] > dp[my2][2]) {
mx2 = a[i];
my2 = i;
}
}
f[a[i]] = i;
}
cout << max(dp[n][0], dp[n][2]) << endl;
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
