CF1842C Tenzing and Balls

这篇博客主要介绍了如何使用动态规划解决 Codeforces 题目 CF1842C “Tenzing and Balls”，并提供了优化思路和完整的代码实现。

题意

给定一个长度为 ${n}$ 的数列，可以选择两个相同的数，并将它们和它们之间的所有数删除。询问最多能删除多少个数。

思路

用 $dp[i]$ 表示数列前 $i$ 个元素最少能保留的个数。对于数列的前 $i$ 项构成的子列，要么对于 $a_i$ 不进行操作，即 $dp[i]=dp[i-1]+1$ ，要么对 $a_i$ 进行操作，找到前面所有与 $a_i$ 相等的项 $a_j$，则 $dp[i]=dp[j-1]$ 。取最小值即可。

值得一提的是，如果每次都暴力找相等的项求最小值，时间复杂度为 $O(n^2)$ ，赛时写的记忆化搜索复杂度也为 $O(n^2)$ ，无法通过。在dp时维护一下每个值的 $dp[j-1]$ 的最小值即可优化为 $O(n)$ 。

代码

int n, a[200010], dp[200010], mn[200010];
void solve() {
    cin >> n;
    rep(i, 0, n) {
        dp[i] = 0;
        mn[i] = INF;
    }
    rep(i, 0, n - 1) {
        cin >> a[i];
        dp[i] = i == 0 ? 1 : min(dp[i - 1] + 1, mn[a[i]]);
        mn[a[i]] = min(mn[a[i]], dp[i - 1]);
    }
    cout << n - dp[n - 1] << endl;
}
int main() {
    ios;
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}