Hỏi cách giải bài toán LIS 2 đầu

[NEZYA]

như đề bài bên trên mình có ý tưởng dùng dùng 1 deque ( mình sẽ đặt là LIS cho tiện gọi ) để lưu dãy tăng dần hiện tại ( tương tự như cách làm LIS nâng cao với chặt nhị phân ) ý tưởng của mình lần lượt là xét giá trị hiện tại nếu:

• giá trị hiện tại < LIS.back() thì push giá trị hiện tại vào cuối LIS ( LIS.push_back() )

• giá trị hiện tại > LIS.front() thì push giá trị hiện tại vào đầu LIS ( LIS.push_front() )

• nếu nằm ngoài trường hợp này mình sẽ tiến hành chặt nhị phân với auto it = lower_bound ( LIS.begin() , LIS.end(), giá trị hiện tại ) và thay thế vị trí con trỏ trả về bằng giá trị hiện tại

cuối cùng mình cout LIS.size()

dưới đây là code của mình:

#include<bits/stdc++.h>
using namespace std;
long long n;
long long inp[100005] = {} ;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for ( int i = 0 ; i < n ; i ++ ){
        cin >> inp[i];
    }
    deque < long long > LIS;
    for ( int i = 0 ; i < n ; i ++ ){
        if ( LIS.empty() || inp[i] < LIS.back() ) LIS.push_back(inp[i]);
        else if ( inp[i] > LIS.front() ) LIS.push_front(inp[i]);
        else{
            auto it = lower_bound ( LIS.begin() , LIS.end() , inp[i] );
            *it = inp[i];
        }
    }
    cout << LIS.size();
    return 0;
}

bài này mình bị WA mà không biết tại sao sai nữa, mọi người tìm được lỗi sai thì giúp mình nhé, mình là thành viên mới của web nên post này có thể còn xấu vs lại khó nhìn mong mọi người thông cảm, cảm ơn mọi người nhiều ạ

[noname00 (HK boy)]

Thuật toán của bạn nom không giống DP lắm, giống tham lam hơn.

[noname00 (HK boy)]

Mình có 1 ví dụ cho bạn:

a = [1 4 2 5 4 5 3]
i = 0 -> lis = [1] (thêm 1 vào đuôi)
i = 1 -> lis = [1 4] (thêm 4 vào đuôi)
i = 2 -> lis = [1 2] (thay 2 vào 4)
i = 3 -> lis = [1 2 5] (thêm 5 vào đuôi)
i = 4 -> lis = [1 2 4] (thay 4 vào 5)
i = 5 -> lis = [1 2 4 5] (thêm 5 vào đuôi)
i = 6 -> lis = [1 2 3 5] (thay 3 vào 4)

Ở bước i = 6, bạn thay 3 vào 2 nhưng thực tế là bạn không thể làm như thế này được. Bản chất dãy lis = [1 2 3 5] là [a[0], a[2], a[6], a[5]], bạn có thể diễn đạt bằng lời các bước nhặt vỏ sò như thế này:

- lấy vỏ sò a[0]
- bỏ qua vỏ sò a[1]
- lấy vỏ sò a[2] và nhét vào cuối
- bỏ qua vỏ sò a[3]
- bỏ qua vỏ sò a[4]
- lấy vỏ sò a[5] và nhét vào cuối
- lấy vỏ sò a[6] và nhét vào đâu đó giữa a[2] và a[5] <- hành vi này không đúng đề bài

Đáp án của bạn có thể đúng trong nhiều trường hợp, nhưng về bản chất logic là sai.

Ở bước else, đáng ra logic phải là:

1. tạm ghi nhận độ dài dãy LIS đến thời điểm hiện tại (độ dài này có tiềm năng là đáp án) -> ans = max(ans, LIS.size())
2. gọi j là index xa nhất trên dãy LIS mà LIS[j] nhỏ hơn vỏ sò thứ i.
3. vứt toàn bộ dãy LIS[j+1 .. cuối] và kết nạp vỏ sò thứ i vào thay thế.

tuy nhiên nếu bạn thật sự cài đặt bước 3 bằng pop_back thì code chắc chắn bị TLE.

Do vậy bạn có thể “cải tiến” cấu trúc dữ liệu LIS bằng 1 mảng “giả” deque như sau:

// mã giả
const int LIM = 100000; // độ dài tối đa của mảng inp
int _dq[2 * LIM + 1]; // khai báo 1 mảng giả dài gấp đôi
int *dq = &_dq[LIM]; // 1 con trỏ trỏ đến chính giữa mảng _dq
int dq_head_idx = 0, dq_tail_idx = -1; // khởi tạo
// trong trường hợp may mắn thì bạn chỉ cần nhét lần lượt từng vỏ sò vào chuỗi (đầu hoặc cuối đều được),
// thì dq[dq_head_idx] (bản chất là _dq[LIM + dq_head_idx]) và dq[dq_tail_idx] (bản chất là _dq[LIM + dq_tail_idx]) sẽ luôn nằm trong mảng _dq

void fake_push_back(int val) {
    dq[++dq_tail_idx] = val;
}

void fake_push_front(int val) {
    dq[--dq_head_idx] = val;
}

bool is_dq_empty() {
    return dq_head_idx > dq_tail_idx;
}

int main() {
    // ... bỏ qua bước đọc

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (is_dq_empty() || inp[i] > dq[dq_tail_idx]) {
            fake_push_back(inp[i]);
        }
        else if (inp[i] < dq[dq_head_idx]) {
            fake_push_front(inp[i]);
        }
        else {
            ans = max(ans, max(0, dq_tail_idx - dq_head_idx + 1)); // cập nhật đáp án mới
            auto it = lower_bound(dq + dq_head_idx, dq + dq_tail_idx, inp[i]); // con trỏ đến vị trí j' đầu tiên mà dq[j] >= inp[i]
            *it = inp[i]; // thay bằng inp[i]
            dq_tail_idx = it - (dq + dq_head_idx); // ghi nhận lại index đuôi mới của dq, toàn bộ phần bên phải từ chỗ đuôi mới trở đi đều bị bỏ qua
        }
    }
    cout << ans;
}

[NEZYA]

em cảm ơn anh nhiều nha, ban đầu em nhìn thấy nó tương tự như LIS bình thường thì em cũng nghĩ là có thể cải tiến bằng Binary Search tương tự như LIS thông thường, mà không ngờ nó có lỗi sai tièm ẩn như vậy, dạ em cảm ơn đã thông não em ạ <3

[Gio (Gió)]

Sao không chia bài toán thành bài toán con: Cho vị trí i, tìm dãy con tăng dài nhất từ 0->i và dãy con giảm dài nhất từ i -> n.
2 bài toán này có thể tính trước và lưu kết quả. Sau đó duyệt và tính dãy dài nhất.