Gợi ý

Thay vì đếm số quả bóng bị xóa ra khỏi hàng, ta có thể đếm số quả bóng còn lại để có được đáp án:

• Gọi ~dp_{i}~ là số quả bóng còn lại ít nhất sau khi xét ~i~ quả bóng đầu.

• Có ~2~ trường hợp:

  1. Giữ lại quả bóng thứ ~i~: ~dp_{i} = dp_{i-1} + 1~.
  2. Loại bỏ quả bóng thứ ~i~: ~dp_{i} = min(dp_{j})~ với ~j+1 < i~ và ~a_{j+1} = a_{i}~.

Với mỗi giá trị ~x~ ta có thể lưu lại giá trị nhỏ nhất của ~dp_{j}~ nên độ phức tạp của thuật toán là ~O(n)~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int n, a[N], dp[N], mn[N];

int main() {
        cin >> n;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) mn[i] = 0x3f;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            //tinh dp[i]
            dp[i] = min(dp[i - 1] + 1, mn[a[i]]);
            //luu lai gia tri min của dp[j]
            mn[a[i]] = min(mn[a[i]], dp[i - 1]);
        }
        cout << n - dp[n] << '\n';
}