Xét một chuỗi số nguyên S bao gồm các phần tử s1, s2, ..., sn. Mỗi phần tử được gán một trọng số theo các quy tắc sau:

(1) Nếu giá trị phần tử âm, trọng số của nó là 0. (2) Nếu giá trị phần tử lớn hơn hoặc bằng 10000, trọng số của nó là 5. Đồng thời, giá trị thực của phần tử được tính là si - 10000. Ví dụ, nếu si = 10101, giá trị thực sẽ là 101 và trọng số là 5. (3) Trong các trường hợp còn lại, trọng số là 1.

Một chuỗi con không giảm của S là một chuỗi con si1, si2, ..., sik, với i1 < i2 < ... < ik, sao cho với mọi 1 ≤ j < k, ta có sij ≤ sij+1.

Chuỗi con không giảm có trọng số lớn nhất là chuỗi con không giảm có tổng trọng số các phần tử là lớn nhất.

Yêu cầu: viết chương trình đọc vào một chuỗi số nguyên và in ra trọng số của chuỗi con không giảm có trọng số lớn nhất.

Ví dụ, với chuỗi đầu vào: 80 75 73 93 73 73 10101 97 -1 -1 114 -1 10113 118

Chuỗi con không giảm có trọng số lớn nhất là: <73, 73, 73, 101, 113, 118> với tổng trọng số là 1+1+1+5+5+1 = 14. Chương trình cần xuất ra giá trị 14.

Độ dài chuỗi đầu vào không vượt quá 2×105.

Định dạng đầu vào

Một danh sách các số nguyên phân tách bởi khoảng trắng: s1, s2, ..., sn.

Định dạng đầu ra

Một số nguyên dương là trọng số của chuỗi con không giảm có trọng số lớn nhất.

Ví dụ đầu vào

80 75 73 93 73 73 10101 97 -1 -1 114 -1 10113 118

Ví dụ đầu ra

14

Phương pháp giải Bài toán có thể được quy về việc tìm độ dài của chuỗi con không giảm dài nhất. Đối với các số có giá trị từ 10000 trở lên, vì trọng số là 5, ta có thể tách chúng thành 5 phần tử có cùng giá trị thực (số ban đầu trừ đi 10000) trong mảng dữ liệu xử lý. Các số âm được bỏ qua (trọng số 0). Như vậy, tổng trọng số của chuỗi con chính bằng số lượng phần tử trong chuỗi con không giảm tìm được từ mảng đã được xử lý này.

Ví dụ minh họa Xét phần tử 10101. Theo quy tắc, giá trị thực là 10101 - 10000 = 101, trọng số là 5. Trong mảng xử lý, ta sẽ thêm 5 phần tử có giá trị 101. Khi tìm chuỗi con không giảm, các phần tử này có thể được chọn, và việc chọn chúng sẽ đóng góp 5 vào tổng độ dài (tức tổng trọng số) của chuỗi con.

Triển khai thuật toán Sử dụng thuật toán tìm chuỗi con không giảm dài nhất với độ phức tạp O(n log n) thông qua mảng "đuôi" và tìm kiếm nhị phân.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 1000010;
int sequence[MAX_SIZE];
int tail[MAX_SIZE];

int main() {
    int value;
    int count = 0;

    while (cin >> value) {
        if (value < 0) {
            continue;
        }
        if (value < 10000) {
            sequence[++count] = value;
        } else {
            int realValue = value - 10000;
            for (int rep =23

 0; rep < 5; ++rep) {
                sequence[++count] = realValue;
            }
        }
    }

    if (count == 0) {
        cout << 0 << endl;
        return 0;
    }

    tail[1] = sequence[1];
    int length = 1;

    for (int idx = 2; idx <= count; ++idx) {
        if (sequence[idx] >= tail[length]) {
            tail[++length] = sequence[idx];
        } else {
            int pos = upper_bound(tail + 1, tail + length + 1, sequence[idx]) - tail;
            tail[pos] = sequence[idx];
        }
    }

    cout << length << endl;
    return 0;
}

Giải thích: Mảng sequence lưu các giá trị đã được xử lý theo quy tắc trọng số. Mảng tail lưu phần tử cuối của các chuỗi con không giảm có độ dài khác nhau. Hàm upper_bound được dùng để tìm vị trí chèn phần tử hiện tại vào mảng tail sao cho mảng này vẫn tăng dần. Kết quả cuối cùng là độ dài của mảng tail, chính là tổng trọng số cần tìm.