[Daimayuan] 三回文序列（C++，前缀和）

给定一个长度为$n$的序列$a$。

我们定义三回文序列是形如a...a⏟k1b...b⏟k2a...a⏟k1\\underbrace{a...a}_{k_1}\\underbrace{b...b}_{k_2}\\underbrace{a...a}_{k_1}k1​a...a​​k2​b...b​​k1​a...a​​的序列，例如:$[1,1,1,2,2,1,1,1]$是一个三回文序列，而$[1,1,1,2,2,2,3,3,3],[1,1,2,2,1]$都不是三回文序列。

现在，希望你找到序列$a$中最长的三回文序列的长度。

注意，k1,k2k_1,k_2k1​,k2​可以为$0$

输入格式

第一行给出一个数字$T$，表示$T$组测试用例

对于每一个测试用例

第一行给出序列的长度$n$

第二行给出序列a1,a2,a3...ana_1,a_2,a_3...a_na1​,a2​,a3​...an​

输出格式

对于每一个测试用例，输出最长的三回文序列的长度。

数据范围

$1\le t\le 2000$

1≤∑n≤2∗1051≤\\sum{n}≤2*10^51≤∑n≤2∗105,1≤ai≤261≤a_i≤261≤ai​≤26

样例输入

6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1

样例输出

7
2
4
1
1
3

解题思路

通过样例，我们注意到三回文序列不一定是连续序列

也就是说1 1 2 2 3 2 1 1的最长三回文序列是1 1 2 2 2 1 1

要想找出最长的三回文序列，我们就需要找出所有三回文序列

首先想到动态规划，但是很难找出最优子结构

然后因为是序列问题，我们想到了前缀和

基本思路：尝试$1$_{$26$的每一种作为$a$，然后尝试所有可能的$k_1$，然后再尝试$1$}$26$的每一种作为$b$，每一种$b$会对应一个k2k_2k2​

这么直接看可能不太容易懂，可以暂时理解一下大概

由这个思路很容易看出我们要采用三重循环来实现

for (int a = 1; a <= 26; a++) {for (int k1 = 0; k1 <= a的总数; k1++) {for (int b = 1; b <= 26; b++) {...}}
}

对应于每一个$a$和k1k_1k1​的组合（$i$和$j$），我们想要知道左右两个索引，以便定下来$b$序列所在的区间

for (int a = 1; a <= 26; a++) {for (int k1 = 0; k1 <= a的总数; k1++) {int l = 左索引, r = 右索引;if (l > r) break;for (int b = 1; b <= 26; b++) {int k2 = [l+1, r-1]范围内b的数量;max_len = max(max_len, k1 * 2 + k2);}}
}

好了，我们的伪代码写完了，接下来是如何把对应部分替换为真正的代码

可以看出，我们有两个要求：

（1）指定$a$的数量k1k_1k1​，我们要求返回它的索引$l,r$

（2）指定某个区间范围，我们要求返回该范围内指定元素$b$的数量

实现方式是维护两个数组sum[26][n], indices[26][n]

sum[i][j]存储的前j个元素的i的数量

indices[i][j]存储的是i的前缀和为j时在序列中的下标

如何使用这两个数组呢？

for (int a = 1; a <= 26; a++) {for (int k1 = 0; k1 <= sum[a][n]; k1++) {int l, r;if (k1) {l = indices[a][k1];r = indices[a][sum[a][n] - k1 + 1];}else {l = 0;r = n + 1;}if (l > r) break;else if (l == r) max_len = max(max_len, 2 * k1 - 1);else {for (int b = 1; b <= 26; b++) {int k2 = sum[b][r - 1] - sum[b][l - 1];max_len = max(max_len, k1 * 2 + k2);}}}
}

最后，AC代码如下

#include <iostream>
using namespace std;
const int max_num = 26;
const int max_len = 2e5;int sum[max_num + 1][max_len + 1], indices[max_num + 1][max_len + 1];int main() {int t, n, x;cin >> t;for (int i = 0; i < t; i++) {cin >> n;for (int j = 1; j <= n; j++) {cin >> x;for (int k = 1; k <= max_num; k++) {sum[k][j] = sum[k][j - 1];}sum[x][j]++;indices[x][sum[x][j]] = j;}int ans = 0;for (int a = 1; a <= 26; a++) {for (int k1 = 0; k1 <= sum[a][n]; k1++) {int l, r;if (k1) {l = indices[a][k1];r = indices[a][sum[a][n] - k1 + 1];}else {l = 0;r = n + 1;}if (l > r) break;else if (l == r) ans = max(ans, 2 * k1 - 1);else {for (int b = 1; b <= 26; b++) {int k2 = sum[b][r - 1] - sum[b][l];ans = max(ans, k1 * 2 + k2);}}}}cout << ans << endl;}return 0;
}