Bài toán mô tả một hệ thống phòng thủ tên lửa có đặc tính: viên đạn đầu tiên có thể bắn tới mọi độ cao, nhưng mỗi viên tiếp theo không được bắn cao hơn viên trước đó. Với một chuỗi tên lửa địch bay tới ở các độ cao khác nhau, ta cần giải quyết hai yêu cầu:

• Tìm số lượng tên lửa tối đa mà một hệ thống có thể chặn được.
• Tìm số lượng hệ thống tối thiểu cần thiết để chặn toàn bộ tên lửa.

Yêu cầu 1: Số tên lửa tối đa bị chặn

Bài toán này tương đương với việc tìm dãy con không tăng dài nhất (Longest Non-Increasing Subsequence). Xét mảng độ cao heights[]. Đặt dp[i] là số lượng tên lửa tối đa có thể chặn nếu kết thúc tại tên lửa thứ i.

Với mỗi cặp chỉ số j < i thỏa mãn heights[j] >= heights[i], ta có thể nối tiếp chuỗi chặn. Khi đó công thức chuyển trạng thái là: dp[i] = max(dp[j] + 1) với mọi j < i và heights[j] >= heights[i]. Kết quả yêu cầu 1 là giá trị lớn nhất trong mảng dp.

Yêu cầu 2: Số hệ thống tối thiểu

Bài toán này tương đương với việc tìm dãy con tăng dài nhất (Longest Increasing Subsequence - LIS). Đặt dp[i] là số hệ thống tối thiểu cần dùng nếu xét tên lửa thứ i là điểm kết thúc của một chuỗi cần hệ thống mới. Nếu heights[j] < heights[i], tên lửa thứ i không thể dùng chung hệ thống với tên lửa thứ j, do đó ta phải tăng số hệ thống. Công thức tương tự: dp[i] = max(dp[j] + 1) cho j < i và heights[j] < heights[i]. Kết quả yêu cầu 2 là giá trị lớn nhất trong mảng dp của phần này.

Cài đặt O(N²) cơ bản

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

const int MAXN = 100005;
int seq[MAXN], dpArr[MAXN];
int total = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int val;
    while (cin >> val) {
        total++;
        seq[total] = val;
    }
    
    int best1 = 0;
    for (int i = 1; i <= total; ++i) {
        dpArr[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (seq[j] >= seq[i]) {
                dpArr[i] = max(dpArr[i], dpArr[j] + 1);
            }
        }
        best1 = max(best1, dpArr[i]);
    }
    cout << best1 << "\n";
    
    int best2 = 0;
    for (int i = 1; i <= total; ++i) {
        dpArr[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (seq[j] < seq[i]) {
                dpArr[i] = max(dpArr[i], dpArr[j] + 1);
            }
        }
        best2 = max(best2, dpArr[i]);
    }
    cout << best2 << "\n";
    
    return 0;
}

Tối ưu thời gian O(N log N)

Để tối ưu, ta thay thế vòng lặp tuyến tính trong tìm max bằng tìm kiếm nhị phân. Cụ thể:

• Yêu cầu 1: Duy trì mảng tail[], trong đó tail[k] lưu giá trị kết thúc nhỏ nhất (hoặc lớn nhất tùy biến) cho dãy không tăng độ dài k. Mảng này có tính đơn điệu, cho phép chèn phần tử mới bằng upper_bound.
• Yêu cầu 2: Duy trì mảng tail2[] cho LIS. Tìm vị trí phù hợp bằng lower_bound để thay thế phần tử, hoặc mở rộng dãy nếu phần tử lớn hơn tất cả.

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

const int MAXN = 100005;
int arr[MAXN], tail1[MAXN], tail2[MAXN];
int cnt = 0;

int main() {
    int x;
    while (scanf("%d", &x) != EOF) {
        arr[++cnt] = x;
    }
    
    // Yêu cầu 1: Dãy không tăng dài nhất
    int len1 = 0;
    tail1[0] = INT_MAX;
    for (int i = 1; i <= cnt; ++i) {
        // Tìm vị trí đầu tiên < arr[i] (vì dãy không tăng)
        int pos = upper_bound(tail1, tail1 + len1 + 1, arr[i], greater<int>()) - tail1;
        if (pos > len1) {
            len1 = pos;
        }
        tail1[pos] = arr[i];
    }
    printf("%d\n", len1);
    
    // Yêu cầu 2: Dãy tăng dài nhất (LIS)
    int len2 = 0;
    tail2[0] = -1;
    for (int i = 1; i <= cnt; ++i) {
        int pos = lower_bound(tail2 + 1, tail2 + len2 + 1, arr[i]) - tail2;
        if (pos > len2) {
            len2 = pos;
        }
        tail2[pos] = arr[i];
    }
    printf("%d\n", len2);
    
    return 0;
}