题目描述

难度分:$1500$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

你可以执行多次如下操作：

• 选择两个下标$i$和$j$，满足$a[i]=a[j]$。删除下标$[i,j]$中的元素。删除后，数组长度减少$i-j+1$。

输出你最多可以删多少个数。

输入样例$1$

2
5
1 2 2 3 3
4
1 2 1 2

输出样例

4
3

算法

动态规划

这个题我尝试了好久的贪心，但是第二个$case$都过不了，没办法只能想想DP，结果发现DP异常简单。

状态定义

定义$dp[i]$表示$a$的前$i$个数中最多可以删多少个数。在这个定义下，答案就是$dp[n]$。

状态转移

1. 不删$a[i]$，状态转移方程为$dp[i]=dp[i-1]$。即$[1,i-1]$中删了多少个数，$[1,i]$中就删除了多少个数。
2. 枚举左边的$a[j](j \lt i)$，如果$a[j]=a[i]$成立，那么删除 $[j,i]$，状态转移方程为$dp[i]=dp[j-1]+(i-j+1)$。

二者取最大值，得$dp[i]=max(dp[i-1], dp[j-1]+i-j+1)$。但是这样单次转移是$O(n)$的，会超时。注意到$dp[j-1]-j+i+1$（把下标一样的放在一起），发现维护一个$premax$数组即可$O(1)$转移，定义$premax[v]$表示$a[i]=v$的$dp[i-1]-i$最大值，于是状态转移方程变为$dp[i]=max(dp[i-1], premax[a[i]]+i+1)$，在计算DP的过程中维护$premax$。

复杂度分析

时间复杂度

状态数量为$O(n)$，单次转移为$O(1)$，所以整体的时间复杂度为$O(n)$。

空间复杂度

DP数组的空间消耗是线性的；而$a[i] \leq n$，所以$premax$数组也是线性的。所以整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int t, n, a[N], dp[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        vector<int> premax(n + 1, -0x3f3f3f3f);
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            dp[i] = max(dp[i], premax[a[i]] + i + 1);
            premax[a[i]] = max(premax[a[i]], dp[i - 1] - i);
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}