Hướng dẫn cho SubSequence

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

Spoiler Alert

Hint 1

  • Xét các trường hợp khi số hiện tại khác hay giống số trước nó --> công thức quy hoạch động

Hint 2

  • Nhận xét: Nếu phần tử hiện tại bằng phần tử trước đó, thì số cách bằng lượng được tính toán trước đó

Có một lượng cal dãy nối với a[i - 1] để tạo thành dãy con biến đổi

Thì tương tự cũng có một lượng cal dãy như thế nối với a[i] = a[i - 1]

  • Nhận xét: Nếu phần tử hiện tại là phần tử chưa từng xuất hiện trước đó, thì số cách bằng lượng kết quả trước đó

Có một lượng b[i - 1] dãy con biến đổi trước đó, mỗi dãy đều có phần tử cuối khác a[i] nên nối được với a[i]

Còn một trường hợp bạn nên cẩn thận là bản thân a[i] cũng là một dãy con biến đổi

  • Nhận xét: Nếu phần tử hiện tại đã từng xuất hiện và bằng phần tử đứng trước, thì số cách bằng lượng kết quả trước đó trừ đi lượng kết quả đã được tính ở vị trí trước đó

Trong b[i - 1] dãy con biến đổi trước đó, có b[M[a[i]] - 1] dãy con biến đổi nối với a[i] tại vị trí M[a[i]] trước đó

Vậy phần còn lại là b[i - 1] - b[M[a[i]] - 1] dãy có phần tử cuối khác a[i] và có thể nối với a[i] để tạo thành dãy con biến đổi

Reference AC code | O(n) time | O(n) auxiliary space | Online Solving, STL, DP_count

C++
/// Input
int n;
cin >> n;

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

vector<int> b(n + 1);            /// Mang ket qua
unordered_map<int, int> M;       /// M[x] la vi tri cuoi xuat hien x
int cal = 1;                     /// Bien tinh toan
b[0] = 0; b[1] = 1; M[a[1]] = 1; /// Base cases
for(int i = 2; i <= n; ++i)
{
    if (a[i] != a[i - 1])
    {
        if (M[a[i]] != 0) /// Neu ton tai phan tu truoc do
            cal = (b[i - 1] - b[M[a[i]] - 1] + MOD) % MOD;
        else
            cal = (b[i - 1] + 1) % MOD;
    }

    b[i] = (b[i - 1] + cal) % MOD; /// Cong them ket qua
    M[a[i]] = i;                   /// Luu lai vi tri cuoi cua ai
}

/// Xuat ket qua
cout << b[n];

Bình luận


  • -7
    THOANGLQDT    6:02 p.m. 29 Tháng 10, 2020

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.