//
//  main.cpp
//  2
//
//  Created by 汪汪队 on 2023/7/8.
//

#include<iostream>
#include<algorithm>
#include<set>
#include<unordered_map>
#include<queue>
#include<vector>
#define int long long
using namespace std;

const int N=200010;

int dp[N];

int min(int a,int b,int c){
    return min(min(a,b),c);
}

void test(){
    int n;
    cin>>n;
    vector<int>p(n+2);
    for (int i=0; i<n; i++) {
        cin>>p[i];
        dp[i]=0x3f3f3f3f;
    }
    unordered_map<int,int>_map;
    dp[0]=1;
    _map[p[0]]=0;
    for (int i=1; i<n; i++) {
        int k=p[i];
        
        if(!_map.count(k)){
            _map[k]=i;
            dp[i]=min(dp[i],dp[i-1]+1);
        }
        
        else{
            
            dp[i]=min(dp[_map[k]-1],dp[i-1]+1,dp[i]);
//            _map[k].push_back(i);
            
            if(dp[i-1]<dp[_map[k]-1]) _map[k]=i;
            
//            for (int j=0; j<_map[k].size(); j++) {
//                if(_map[k][j]==0){
//                    dp[i]=0;
//                    break;
//                }
//                dp[i]=min(dp[_map[k][j]-1],dp[i-1]+1,dp[i]);
//            }
            
        }
        
    }
    
//    for (int i=0; i<n; i++) {
//        cout<<dp[i]<<" ";
//    }
//    cout<<endl;

    cout<<n-dp[n-1]<<endl;
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin>>n;
    while (n--) {
        test();
    }
    
    return 0;
}

F. Tenzing and Balls

Solution

Analysis

我们用数值来代表每个小球的颜色，题意即为每次操作可以取出序列中两个数值相同的之间的所有数（包括这两个数），并且将序列变成删除子序列后的新序列。

分析题目，显然：

• 对于 \(a < b < c < d\) 显然我们不可能删除同时范围 \((a, c)\) 和 \((b, d)\) ，因为当我们删除序列 \([a, c]\) 后序列将会变成 \([c, d]\) 。

• 如果我们同时删除范围 \((a, d)\) 和 \((b, c)\) ，最终得到的新序列应该与仅删除范围 \((a, d)\) 结果相同，换句话说：当序列 \([b, c] \subset [a, d]\) 时，结果即为删除序列 \([a, d]\) ，我们只需要进行一次操作即可。

那么，经过上述分析，我们可以假设：

在我们所寻求的最优解中，所有删除的子序列都是不相交的。

因此，问题等价为：我们需要找到一些不相交的子序列集合 \(A_n = \{ a[l_i, r_i], i\in [1, n] \}\) ，

使得对于 \(\forall \ a[l_i, r_i] \bigcap a[l_j, r_j] = \varnothing (i,j \in [1,n])\) 并且 \(a[l_i] = a[r_i]\) ，同时我们也需要最大化 \(\sum_{i=1}^n (r_i - l_i + 1)\) 的值。

Conclusion

考虑使用动态规划解决等价问题，令 \(dp_i\) 代表在子序列前端 \(a[1 \cdots n]\) 中==不删除的点==的最小数量，那么最终我们需要的最大值就是总数量减去前 \(n\) 个数中不删除的点的最小数量。

分析状态转移，用 \(j\) 来代表我们状态转移中寻求的索引，\(dp_j\) 即代表为每个数值 \(x\) 存储的满足 \(a[j+1]=x\) 的最小值，分析能否寻找到这样的索引 \(j\) ，我们可以得到：

• 如果我们无法寻找到一个索引 \(j\) 使得 \(a[j+1] = a[i]\) ，即我们无法删除子序列 \(a[j+1 \cdots i]\) ，此时状态转移为 \(dp_i = dp_{i-1} + 1\) 。
• 若果我们可以寻找到一个索引 \(j\) 使得 \(a[j+1] = a[i]\) ，即我们能够删除子序列 \(a[j+1 \cdots i]\) ，此时状态转移为在 \(a[j+1]=a[i] \) 且 \(j + 1 < i\) 的情况下求解 \(dp_i = min\{dp_j\}\) 。

综合所有情况，我们得出最终的状态转移方程：
\[
dp_i = min(dp_{i - 1} + 1, \ min\{dp_j | j+1<i, a[j+1]=a[i]\})
\]
我们预先为每个数值 \(x\) 存储满足 \(a[j + 1] = x\) 的最小 \(dp_j\) ，这样计算每个 \(dp\) 的时间复杂度为 \(\Theta(n)\) 。

Code

#include <bits/stdc++.h>
#define mod 998244353
#define N 200005
#define INI 1000000000
using namespace std;
using ll = long long int;

int n, a[N], dp[N], mn[N];
 
void solve()
{
    cin >> n;
    dp[0] = 0; dp[1] = 0;
    for(int i = 1; i <= n; i++)
    {
        mn[i] = INI;
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = min(dp[i - 1] + 1, mn[a[i]]);
        mn[a[i]] = min(mn[a[i]], dp[i - 1]);
    }
    cout << n - dp[n] << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}