Dãy con hình nón với C++ (Full thuật toán + Code)

Đây là đề thi học sinh giỏi cấp tỉnh môn Tin học của tỉnh Yên Bái năm học 2022-2023. Câu số 4 (3 điểm) là câu khó nhất của bộ đề thi. Xin mời các bạn tham khảo các thuật toán để giải bài này cũng như phần code của các thuật toán được trình bày ở dưới đây:

NỘI DUNG

Nội dung Bài tập

Một dãy số có độ dài (số phần tử) là m được gọi là dãy hình nón nếu nó là một dãy gồm các số nguyên dương và có các đặc điểm sau:

Số lượng phần tử của dãy là một số lẻ (hay m = 2 * x + 1);
Không có hai số nào đứng cạnh nhau trong dãy có giá trị bằng nhau;
x + 1 số đầu tiên của dãy là một dãy tăng;
x + 1 số cuối cùng của dãy là một dãy giảm.

Ví dụ: Dãy 3 6 9 5 2 là một dãy hình nón có độ dài bằng 5; dãy 1 8 3 6 9 không phải là dãy hình nón.

Cho dãy A gồm n số nguyên dương a₁, a₂, …, a_n. Một dãy con của A là một dãy được tạo ra bằng cách lấy ra một số phần tử trong A nhưng giữ nguyên thứ tự (các phần tử có thể không liên tiếp nhau).

Yêu cầu: Trong các dãy con của A hãy tìm độ dài của dãy con hình nón dài nhất.

Để giải bài toán này, chúng ta cần tìm độ dài của dãy con hình nón dài nhất trong dãy A. Dãy con hình nón có các đặc điểm như đã mô tả trong đề bài. Chúng ta sẽ sử dụng phương pháp quy hoạch động để giải quyết bài toán này.

Thuật toán quy hoạch động

Tạo hai mảng inc và dec:
- inc[i]: Là độ dài của dãy tăng dài nhất kết thúc tại A[i].
- dec[i]: Là độ dài của dãy giảm dài nhất bắt đầu từ A[i].
Tính mảng inc:
- Duyệt từ đầu đến cuối dãy A, nếu A[i] > A[j] với j < i, thì inc[i] = max(inc[i], inc[j] + 1).
Tính mảng dec:
- Duyệt từ cuối về đầu dãy A, nếu A[i] > A[j] với j > i, thì dec[i] = max(dec[i], dec[j] + 1).
Tìm độ dài dãy con hình nón dài nhất:
- Duyệt qua từng phần tử của dãy A, và tính độ dài dãy con hình nón tại mỗi vị trí i bằng công thức inc[i] + dec[i] - 1.
- Lưu ý rằng inc[i] + dec[i] - 1 phải là số lẻ để thỏa mãn điều kiện của dãy hình nón.

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    vector<int> inc(n, 1); // Mảng lưu độ dài dãy tăng dài nhất kết thúc tại A[i]
    vector<int> dec(n, 1); // Mảng lưu độ dài dãy giảm dài nhất bắt đầu từ A[i]

    // Tính mảng inc
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (A[i] > A[j] && inc[i] < inc[j] + 1) {
                inc[i] = inc[j] + 1;
            }
        }
    }

    // Tính mảng dec
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (A[i] > A[j] && dec[i] < dec[j] + 1) {
                dec[i] = dec[j] + 1;
            }
        }
    }

    // Tìm độ dài dãy con hình nón dài nhất
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        int total = inc[i] + dec[i] - 1;
        if (total % 2 == 1 && total > maxLen) {
            maxLen = total;
        }
    }

    return maxLen;
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Giải thích:

Mảng inc: Lưu độ dài của dãy tăng dài nhất kết thúc tại mỗi phần tử A[i].
Mảng dec: Lưu độ dài của dãy giảm dài nhất bắt đầu từ mỗi phần tử A[i].
Tính toán độ dài dãy con hình nón: Độ dài dãy con hình nón tại mỗi vị trí i là inc[i] + dec[i] - 1. Chúng ta chỉ quan tâm đến các giá trị lẻ của tổng này.

Độ phức tạp:

Độ phức tạp thời gian của thuật toán là O(n^2) do chúng ta sử dụng hai vòng lặp lồng nhau để tính inc và dec.
Độ phức tạp không gian là O(n) do sử dụng hai mảng phụ inc và dec.

Kết quả:

Chương trình sẽ in ra độ dài của dãy con hình nón dài nhất trong dãy A. Ví dụ với dãy {3, 6, 9, 5, 2}, kết quả sẽ là 5.

Bài toán tìm độ dài dãy con hình nón dài nhất có thể được giải quyết bằng nhiều cách khác nhau, tùy thuộc vào yêu cầu về độ phức tạp thời gian và không gian. Dưới đây là một số phương pháp khác có thể áp dụng:

Thuật toán Binary Search kết hợp với Quy hoạch động

Ý tưởng: Thay vì sử dụng hai vòng lặp lồng nhau để tính inc và dec, chúng ta có thể sử dụng Binary Search để tối ưu hóa việc tìm kiếm vị trí chèn trong quá trình tính toán.
Độ phức tạp: O(n log n) cho mỗi mảng inc và dec.
Cách thực hiện:
- Sử dụng Binary Search để duy trì một mảng tạm thời (temp) chứa các phần tử tăng dần hoặc giảm dần.
- Khi duyệt qua từng phần tử của dãy A, sử dụng Binary Search để tìm vị trí chèn phù hợp trong mảng tạm thời.
- Cập nhật độ dài của dãy tăng hoặc giảm tại mỗi vị trí.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    vector<int> inc(n, 1); // Mảng lưu độ dài dãy tăng dài nhất kết thúc tại A[i]
    vector<int> dec(n, 1); // Mảng lưu độ dài dãy giảm dài nhất bắt đầu từ A[i]

    // Tính mảng inc sử dụng Binary Search
    vector<int> temp;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(temp.begin(), temp.end(), A[i]);
        if (it == temp.end()) {
            temp.push_back(A[i]);
        } else {
            *it = A[i];
        }
        inc[i] = temp.size();
    }

    // Tính mảng dec sử dụng Binary Search
    temp.clear();
    for (int i = n - 1; i >= 0; i--) {
        auto it = lower_bound(temp.begin(), temp.end(), A[i]);
        if (it == temp.end()) {
            temp.push_back(A[i]);
        } else {
            *it = A[i];
        }
        dec[i] = temp.size();
    }

    // Tìm độ dài dãy con hình nón dài nhất
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        int total = inc[i] + dec[i] - 1;
        if (total % 2 == 1 && total > maxLen) {
            maxLen = total;
        }
    }

    return maxLen;
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Thuật toán Stack

Ý tưởng: Sử dụng Stack để duy trì các phần tử tăng hoặc giảm trong quá trình duyệt dãy.
Độ phức tạp: O(n) cho mỗi mảng inc và dec.
Cách thực hiện:
- Duyệt dãy A từ đầu đến cuối để tính inc:
  - Sử dụng Stack để lưu các phần tử tăng dần.
  - Khi gặp phần tử lớn hơn phần tử trên đỉnh Stack, đẩy vào Stack và cập nhật inc[i].
- Duyệt dãy A từ cuối về đầu để tính dec:
  - Sử dụng Stack để lưu các phần tử giảm dần.
  - Khi gặp phần tử lớn hơn phần tử trên đỉnh Stack, đẩy vào Stack và cập nhật dec[i].

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    vector<int> inc(n, 1); // Mảng lưu độ dài dãy tăng dài nhất kết thúc tại A[i]
    vector<int> dec(n, 1); // Mảng lưu độ dài dãy giảm dài nhất bắt đầu từ A[i]

    // Tính mảng inc sử dụng Stack
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && A[st.top()] >= A[i]) {
            st.pop();
        }
        if (!st.empty()) {
            inc[i] = inc[st.top()] + 1;
        }
        st.push(i);
    }

    // Tính mảng dec sử dụng Stack
    while (!st.empty()) st.pop(); // Clear stack
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && A[st.top()] >= A[i]) {
            st.pop();
        }
        if (!st.empty()) {
            dec[i] = dec[st.top()] + 1;
        }
        st.push(i);
    }

    // Tìm độ dài dãy con hình nón dài nhất
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        int total = inc[i] + dec[i] - 1;
        if (total % 2 == 1 && total > maxLen) {
            maxLen = total;
        }
    }

    return maxLen;
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Thuật toán Fenwick Tree (BIT) hoặc Segment Tree

Ý tưởng: Sử dụng cấu trúc dữ liệu Fenwick Tree hoặc Segment Tree để tối ưu hóa việc tìm kiếm và cập nhật các giá trị trong quá trình tính toán.
Độ phức tạp: O(n log n) cho mỗi mảng inc và dec.
Cách thực hiện:
- Sử dụng Fenwick Tree hoặc Segment Tree để lưu trữ và truy vấn các giá trị tối ưu trong quá trình tính toán inc và dec.
- Khi duyệt qua từng phần tử của dãy A, sử dụng cấu trúc dữ liệu để tìm giá trị lớn nhất hoặc nhỏ nhất trong một khoảng nhất định.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class FenwickTree {
private:
    vector<int> tree;

public:
    FenwickTree(int size) {
        tree.resize(size + 1, 0);
    }

    void update(int index, int value) {
        while (index < tree.size()) {
            tree[index] = max(tree[index], value);
            index += index & -index;
        }
    }

    int query(int index) {
        int result = 0;
        while (index > 0) {
            result = max(result, tree[index]);
            index -= index & -index;
        }
        return result;
    }
};

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    // Nén dữ liệu để phù hợp với Fenwick Tree
    vector<int> sortedA = A;
    sort(sortedA.begin(), sortedA.end());
    sortedA.erase(unique(sortedA.begin(), sortedA.end()), sortedA.end());

    vector<int> inc(n, 1); // Mảng lưu độ dài dãy tăng dài nhất kết thúc tại A[i]
    vector<int> dec(n, 1); // Mảng lưu độ dài dãy giảm dài nhất bắt đầu từ A[i]

    // Tính mảng inc sử dụng Fenwick Tree
    FenwickTree ftInc(sortedA.size());
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(sortedA.begin(), sortedA.end(), A[i]) - sortedA.begin();
        inc[i] = ftInc.query(pos) + 1;
        ftInc.update(pos + 1, inc[i]);
    }

    // Tính mảng dec sử dụng Fenwick Tree
    FenwickTree ftDec(sortedA.size());
    for (int i = n - 1; i >= 0; i--) {
        int pos = lower_bound(sortedA.begin(), sortedA.end(), A[i]) - sortedA.begin();
        dec[i] = ftDec.query(pos) + 1;
        ftDec.update(pos + 1, dec[i]);
    }

    // Tìm độ dài dãy con hình nón dài nhất
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        int total = inc[i] + dec[i] - 1;
        if (total % 2 == 1 && total > maxLen) {
            maxLen = total;
        }
    }

    return maxLen;
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Thuật toán Divide and Conquer

Ý tưởng: Chia dãy A thành các phần nhỏ hơn, giải quyết từng phần và kết hợp kết quả.
Độ phức tạp: O(n log n) hoặc O(n^2) tùy cách triển khai.
Cách thực hiện:
- Chia dãy A thành hai nửa, tìm dãy con hình nón dài nhất trong mỗi nửa.
- Kết hợp kết quả từ hai nửa bằng cách tìm dãy con hình nón dài nhất đi qua điểm giữa.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestConeSequenceHelper(vector<int>& A, int left, int right) {
    if (left == right) return 1;

    int mid = (left + right) / 2;

    // Tìm dãy con hình nón dài nhất trong nửa trái và nửa phải
    int leftMax = longestConeSequenceHelper(A, left, mid);
    int rightMax = longestConeSequenceHelper(A, mid + 1, right);

    // Tìm dãy con hình nón dài nhất đi qua điểm giữa
    int inc = 1, dec = 1;
    for (int i = mid - 1; i >= left; i--) {
        if (A[i] < A[i + 1]) inc++;
        else break;
    }
    for (int i = mid + 1; i <= right; i++) {
        if (A[i] < A[i - 1]) dec++;
        else break;
    }

    int total = inc + dec - 1;
    if (total % 2 == 0) total--; // Đảm bảo độ dài là số lẻ

    return max({leftMax, rightMax, total});
}

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    return longestConeSequenceHelper(A, 0, n - 1);
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Thuật toán Greedy kết hợp với Quy hoạch động

Ý tưởng: Sử dụng thuật toán tham lam để chọn các phần tử phù hợp trong quá trình tính toán inc và dec.
Độ phức tạp: O(n) hoặc O(n log n) tùy cách triển khai.
Cách thực hiện:
- Duyệt dãy A và chọn các phần tử tăng hoặc giảm một cách tham lam.
- Kết hợp với quy hoạch động để lưu trữ kết quả tối ưu.

Ý tưởng:

Tính mảng inc (dãy tăng dài nhất kết thúc tại A[i]):
- Sử dụng một mảng tạm thời temp để lưu các phần tử tăng dần.
- Khi duyệt qua từng phần tử của dãy A, sử dụng Binary Search để tìm vị trí chèn phù hợp trong temp.
- Nếu phần tử hiện tại lớn hơn tất cả các phần tử trong temp, thêm nó vào cuối temp.
- Ngược lại, thay thế phần tử nhỏ nhất trong temp mà lớn hơn hoặc bằng phần tử hiện tại.
- Độ dài của temp tại mỗi bước chính là giá trị của inc[i].
Tính mảng dec (dãy giảm dài nhất bắt đầu từ A[i]):
- Tương tự như tính inc, nhưng duyệt dãy A từ cuối về đầu và sử dụng một mảng tạm thời để lưu các phần tử giảm dần.
Tìm độ dài dãy con hình nón dài nhất:
- Duyệt qua từng phần tử của dãy A, tính tổng inc[i] + dec[i] - 1.
- Chỉ xét các tổng có độ dài lẻ và tìm giá trị lớn nhất.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    vector<int> inc(n, 1); // Mảng lưu độ dài dãy tăng dài nhất kết thúc tại A[i]
    vector<int> dec(n, 1); // Mảng lưu độ dài dãy giảm dài nhất bắt đầu từ A[i]

    // Tính mảng inc sử dụng Greedy kết hợp Binary Search
    vector<int> tempInc;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tempInc.begin(), tempInc.end(), A[i]);
        if (it == tempInc.end()) {
            tempInc.push_back(A[i]);
        } else {
            *it = A[i];
        }
        inc[i] = tempInc.size();
    }

    // Tính mảng dec sử dụng Greedy kết hợp Binary Search
    vector<int> tempDec;
    for (int i = n - 1; i >= 0; i--) {
        auto it = lower_bound(tempDec.begin(), tempDec.end(), A[i]);
        if (it == tempDec.end()) {
            tempDec.push_back(A[i]);
        } else {
            *it = A[i];
        }
        dec[i] = tempDec.size();
    }

    // Tìm độ dài dãy con hình nón dài nhất
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        int total = inc[i] + dec[i] - 1;
        if (total % 2 == 1 && total > maxLen) {
            maxLen = total;
        }
    }

    return maxLen;
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Thuật toán Two Pointers

Ý tưởng: Sử dụng hai con trỏ để duyệt dãy A và tìm dãy con hình nón dài nhất.
Độ phức tạp: O(n) nếu áp dụng được.
Cách thực hiện:
- Duyệt dãy A với hai con trỏ, một ở đầu và một ở cuối.
- Di chuyển các con trỏ để tìm dãy con hình nón dài nhất.

#include <iostream>
#include <vector>

using namespace std;

int longestConeSequence(vector<int>& A) {
    int n = A.size();
    if (n == 0) return 0;

    int maxLen = 1;
    int left = 0, right = 0;

    while (right < n) {
        // Tìm dãy tăng
        while (right + 1 < n && A[right] < A[right + 1]) {
            right++;
        }

        // Tìm dãy giảm
        while (right + 1 < n && A[right] > A[right + 1]) {
            right++;
        }

        // Tính độ dài dãy con hình nón
        int len = right - left + 1;
        if (len % 2 == 1 && len > maxLen) {
            maxLen = len;
        }

        left = right;
        right++;
    }

    return maxLen;
}

int main() {
    vector<int> A = {3, 6, 9, 5, 2};
    cout << "Do dai day con hinh non dai nhat: " << longestConeSequence(A) << endl;
    return 0;
}

Lựa chọn phương pháp phù hợp:

Nếu yêu cầu độ phức tạp thời gian thấp (O(n log n)), nên sử dụng Binary Search hoặc Fenwick Tree/Segment Tree.
Nếu yêu cầu độ phức tạp không gian thấp, có thể sử dụng Stack hoặc Two Pointers.
Nếu dữ liệu đầu vào nhỏ (n ≤ 1000), phương pháp quy hoạch động với độ phức tạp O(n^2) là đủ.

Lập trình C/C++