Hiểu bài toán

Cho một dãy số A gồm N phần tử. Nhiệm vụ của bạn là tìm số lượng phần tử tối thiểu cần xóa để dãy còn lại có tính chất: dãy con tăng dần (không nhất thiết liên tiếp) hoặc dãy con giảm dần (không nhất thiết liên tiếp). Nói cách khác, ta cần tìm độ dài của dãy con dài nhất có tính chất tăng hoặc giảm, sau đó trả về số phần tử còn lại cần xóa (N - độ dài dãy con dài nhất đó).

Các cách tiếp cận

Cách Tối ưu hóa với Quy hoạch động và Cấu trúc dữ liệu (Fenwick Tree)

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define el '\n'
#define all(x) x.begin(), x.end()
typedef long long ll;
using pii = pair<int,int>;
const int MOD = 1e9 + 7;
using ull = unsigned long long;

const int maxN = (int) 1e5 + 6;

int BIT[maxN];
int n, a[maxN];
vector<int> v;

void add(int idx, int val){
    for(; idx < maxN; idx += idx&-idx) BIT[idx] = max(BIT[idx], val);
}

int get(int idx){
    int res = 0;
    for(; idx > 0; idx -= idx&-idx) res = max(res, BIT[idx]);
    return res;
}

int solveLIS() {
    memset(BIT, 0, sizeof(BIT));
    v.clear();
    for(int i = 1; i <= n; i++) v.pb(a[i]);
    sort(all(v));
    v.resize(unique(all(v)) - v.begin());

    int maxLen = 0;
    for(int i = 1; i <= n; i++){
        int pos = lower_bound(all(v), a[i]) - v.begin() + 1;
        int len = get(pos - 1) + 1;
        add(pos, len);
        maxLen = max(maxLen, len);
    }
    return maxLen;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen("tree.inp", "r")) {
        freopen("tree.inp", "r", stdin);
        freopen("tree.out", "w", stdout);
    }

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int inc = solveLIS();

    // Dao nguoc gia tri de tim LDS
    for(int i = 1; i <= n; i++) a[i] = -a[i];
    int dec = solveLIS();

    cout << n - max(inc, dec);
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là cách tiếp cận tối ưu để giải quyết bài toán. Ta sử dụng cấu trúc dữ liệu Fenwick Tree (cây BIT) để tối ưu hóa việc tìm độ dài dãy con tăng dần dài nhất (LIS).

1. Bình thường hóa giá trị (Coordinate Compression): Do giá trị của A có thể lớn (lên tới 10^9), ta cần chuẩn hóa chúng về các chỉ số từ 1 đến N để sử dụng được BIT.
2. Tìm LIS: Duyệt từng phần tử a[i], ta cần tìm độ dài dãy con tăng dần dài nhất kết thúc bởi một phần tử nhỏ hơn a[i]. Fenwick Tree giúp ta query giá trị max trong khoảng [1, pos - 1] trong thời gian O(log N).
3. Tìm LDS: Tương tự, ta đảo dấu toàn bộ mảng A (nhân với -1) và thực hiện lại thuật toán tìm LIS. Kết quả của LIS trên mảng đảo chính là độ dài của LDS (Longest Decreasing Subsequence) của mảng ban đầu.
4. Kết quả: Số phần tử cần xóa là N - max(LIS, LDS).

Cách Sử dụng hàm có sẵn (Lower Bound)

#include <bits/stdc++.h>
using namespace std;

int LIS(vector<int> &a)
{
    vector<int> tail;
    for(int x : a)
    {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if(it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    return tail.size();
}

int main()
{
    ifstream fin("TREE.INP");
    ofstream fout("TREE.OUT");

    int N;
    fin >> N;
    vector<int> a(N);
    for(int i=0; i<N; i++) fin >> a[i];

    int inc = LIS(a);

    // Để tìm LDS, đảo dấu tất cả phần tử và tính LIS
    vector<int> b(N);
    for(int i=0; i<N; i++) b[i] = -a[i];
    int dec = LIS(b);

    int ans = N - max(inc, dec);
    fout << ans;

    fin.close();
    fout.close();
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Phương pháp này sử dụng kỹ thuật 'tail array' (mảng đuôi) để tìm LIS một cách hiệu quả.

1. Mảng đuôi (tail): Mảng tail lưu các phần tử cuối cùng của các dãy con tăng dần có độ dài khác nhau. Ví dụ, tail[i] là phần tử cuối cùng nhỏ nhất có thể của một dãy con tăng dần có độ dài i+1.
2. Cập nhật: Duyệt mỗi phần tử x trong mảng:
   • Sử dụng lower_bound để tìm vị trí đầu tiên trong tail có giá trị >= x.
   • Nếu không tìm thấy (tức là x lớn hơn tất cả các phần tử trong tail), ta thêm x vào cuối tail (tăng độ dài LIS).
   • Nếu tìm thấy, ta thay thế phần tử tại vị trí đó bằng x (giữ cho các phần tử trong tail nhỏ nhất có thể).
3. LDS: Tương tự cách 1, ta nhân tất cả phần tử với -1 và gọi hàm LIS.
4. Ưu điểm: Code ngắn gọn, dễ hiểu, tận dụng hàm lower_bound của STL C++.

Cách Quy hoạch động cơ bản (O(N^2))

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    // DP cho LIS
    vector<int> dp_inc(n, 1);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[j] < a[i]) {
                dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1);
            }
        }
    }

    // DP cho LDS
    vector<int> dp_dec(n, 1);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[j] > a[i]) {
                dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1);
            }
        }
    }

    int max_len = 0;
    for(int i = 0; i < n; i++) {
        max_len = max(max_len, max(dp_inc[i], dp_dec[i]));
    }

    cout << n - max_len;
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Đây là phương pháp cơ bản nhất sử dụng quy hoạch động.

1. Mảng DP: Dùng mảng dp_inc[i] để lưu độ dài dãy con tăng dần dài nhất kết thúc tại vị trí i. Tương tự cho dp_dec.
2. Công thức: dp_inc[i] = max(dp_inc[j] + 1) với mọi j < i và a[j] < a[i].
3. Nhược điểm: Với N lớn (ví dụ 10^5), thuật toán này sẽ chạy quá thời gian do thực hiện khoảng 5*10^9 phép tính. Nó chỉ phù hợp cho N nhỏ (< 5000).

Lưu ý: Trong các bài nộp thực tế, các giải pháp thường kết hợp quy hoạch động với cấu trúc dữ liệu tối ưu (Fenwick Tree) hoặc kỹ thuật mảng đuôi như đã trình bày ở trên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán tìm số phần tử xóa ít nhất để dãy thành dãy đơn điệu (tăng hoặc giảm) tương đương bài toán tìm dãy con dài nhất có tính chất đơn điệu (LIS hoặc LDS).
• Để tìm LDS (Longest Decreasing Subsequence), ta có thể biến đổi mảng bằng cách nhân tất cả các phần tử với -1 và tìm LIS của mảng mới.
• Kỹ thuật dùng mảng tail kết hợp với lower_bound cho phép tìm LIS trong thời gian O(N log N) mà không cần dùng Fenwick Tree.

Lỗi thường gặp

• Nhầm lẫn giữa dãy con liên tiếp và dãy con không liên tiếp. Bài toán này yêu cầu dãy con không nhất thiết phải liên tiếp.
• Xử lý sai đối với các số âm hoặc số trùng nhau khi sử dụng lower_bound (thường cần dùng lower_bound cho LIS và upper_bound trong một số trường hợp đặc biệt, nhưng với bài toán này lower_bound là phù hợp).
• Quên xử lý IO nhanh (iosbase::syncwith_stdio) hoặc dùng cin/cout thay vì fin/fout có thể gây trễ khi nộp bài.