题目大意
给你一个数组 $a[1\cdots n]$,每一次操作,如果 $a_i \neq a_{i+1}$,可以将 $a_i, a_{i+1}$ 都删掉
删掉之后剩下的数拼接起来
经过若干次这样操作之后,最后要使得数组中所有元素都相同
那么最后的数组最大长度是多少
思路分析
由于操作之后数组中所有元素都相同,$n \leqslant 5000$,所以可以枚举操作完成后,数组中相同元素的值 $x$
一开始可以对 $x$ 出现的所有位置打表,记 $x$ 出现的第 $i$ 个位置是 $\displaystyle f_x(i)$
只考虑 $x$ 出现的位置,从 $i-1 \to i$
对于区间 $[f_x(i-1)\cdots f_x(i)]$,如果中间的数 $[f_x(i-1)+1, f_x(i)-1]$ 能全部消去
那么就存在转移 $f_x(i) = f_x(i-1) + 1$
其中 $f_x(i)$ 表示第 $i$ 个 $x$ 这个位置,得到的数组的最大长度
这样就启发我们用 $dp$ 来实现
$dp(i)$ 表示 $i$ 位置的这个数最终保留下来,并且作为序列结尾,能得到的序列最大长度
那么存在 $dp(i) = \max(dp(j) + 1) \quad (a_j = a_i, \ 1 \leqslant j \leqslant i-1)$ 的转移
当且仅当 $[j+1, i-1]$ 中的数可以消去
要想保留 $a_i$,那么 $dp$ 的起点一定是找到第一个 $x = a_i$ 所在的位置 $s$
令 $dp(s) = 1$,然后递推
一开始的时候,所有点的 $dp$ 值都是 $0$,先预处理一下
如果 $[1\cdots i-1]$ 的前缀可以消去,那么 $i$ 就可以作为 $dp$ 的起点,$dp(i) = 1$
接着按上面的方法递推就可以
接下来的难点就是,什么时候 $[l, r]$ 中的元素可以全部消去?不妨设 $[l, r]$ 中的元素个数为 $n$
-
$n$ 必须是偶数,这根据题意很容易发现
-
实际上消去的充要条件是,对 $[l, r]$ 中的每一个数 $x$,都能找到一个 $y \neq x$ 与它匹配
对于出现次数最大的数 $x$
$x$ 如果出现次数 $> n/2$,必然有某个 $x$ 找不到匹配,否则一定是可以的
证明如下,如果出现次数最多的数 $x$ 出现的次数都 $\leqslant n/2$,那么最坏的情况
就是序列一段都是 $x$,最前面的 $x$ 能消去,那么一整段都可以消去
这是可能的,因为我们可以贪心地考虑 $[2\cdots, n/2]$
这些 $x$ 从后往前依次和 $[n/2+1 \cdots n]$ 这些 $y \neq x$ 配对删除
再来看看充分性
如果有一个数 $x$ 出现次数 $k > n/2$,那么其他元素的个数是 $n - k$
因为其他元素都要被删除,所以还剩下无法匹配的 $x$ 个数是 $n - 2(n-k) > 0$
这显然是不符合全部删除的要求的
最后计算答案的时候,因为每一个位置 $i$ 都可能作为序列的结尾
根据之前的分析,$dp(i)$ 是 $i$ 这个位置保留下来并且作为序列结尾,能够得到的最大长度
如果 $[i+1, n]$ 这一段能够完全删除,那么就可以对所有这样的 $dp(i)$ 取一个 $\max$ 就是答案
int main() {
//freopen("input.txt", "r", stdin);
int cas;
cin >> cas;
while (cas--) {
int n;
cin >> n;
vector<int> a(n+1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<vector<int> > candel(n+1, vector<int>(n+1, 0));
for (int i = 1; i <= n; i++) {
int mx = 0;
vector<int> cnt(n+1, 0);
for (int j = i; j <= n; j++) {
cnt[a[j]]++;
chmax(mx, cnt[a[j]]);
if ((j-i+1) % 2 == 0 && mx <= (j-i+1)/2) candel[i][j] = 1;
}
}
vector<int> dp(n+1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (candel[1][i-1]) dp[i] = 1;
else dp[i] = -0x3f;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] != a[i]) continue;
if (j == i-1 || candel[j+1][i-1]) chmax(dp[i], dp[j] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) if (i == n || candel[i+1][n]) chmax(ans, dp[i]);
cout << ans << endl;
}
}
很详细666