Hỏi về thuật toán bài tập

[mark123 (Mark)]

Luyện Code Online - Học lập trình tương tác trực tuyến

MINE - Đào vàng

Đề bài

Một nhóm nhân viên khai mỏ có dự định tiến vào một hầm mỏ dài và rất hẹp. Vì rất hẹp và dài, nên chỉ người vào cuối cùng mới có thể rời khỏi hầm mỏ. Ban đầu, hầm mỏ trống. Ở cửa hầm mỏ, chúng ta ghi lại thời gian một ai đó vào và ra hầm mỏ. Mỗi người thợ mỏ không được ở trong hầm mỏ quá m đơn vị thời gian. Hãy đếm xem có bao nhiêu tình huống khác nhau có thể xảy ra. Hai tình huống được xem là khác nhau, nếu tồn tại một thời điểm nào đó mà trong tình huống này, người i có trong hầm mỏ, trong tình huống khác, người i không có trong hầm mỏ. Các công nhân khai mỏ được đánh số từ 1 đến n. Công nhân khai mỏ thứ i không được vào hầm mỏ trước công nhân khai mỏ thứ i – 1(Công nhân 1 là người vào đầu tiên).

Dữ liệu vào

• Dòng đầu ghi hai số nguyên n và m, trong đó 1 ≤ n ≤ 2.10^5 và 1 ≤ m ≤ 10^6
• Dòng thứ hai ghi 2n số nguyên dương 1 ≤ a1 < a2 < … < a2n ≤ 10^6 là thời điểm (tính từ đầu ngày) có một người thợ mỏ vào hoặc ra hầm mỏ

Giới hạn:

• 10% số test có n ≤ 10
• 10% số test khác có n ≤ 200, m = 10^6
• 30% số test khác có n ≤ 200
• 40% số test khác có n ≤ 2000
• 10% số test còn lại không có ràng buộc gì thêm

Dữ liệu ra

• In ra kết quả sau khi chia dư cho 1000003

Ví dụ
Input 1
3 6 1 2 3 7 9 10
Output 1
2

các anh chị có thể chỉ em thuật toán bài này hoặc em xin tài liệu về dạng bài như này được không ạ? em có tra gg rồi nhưng không có ạ

[mark123 (Mark)]

các anh chị có thể chỉ em thuật toán bài này hoặc em xin tài liệu về dạng bài như này được không ạ? em có tra gg rồi nhưng không có ạ

[minhtuan_998]

bạn google kỹ chưa ?

#include <bits/stdc++.h>
const int N = 8e3 + 5, MOD = 1e6 + 3, M = 4e5 + 5;
using namespace std;
long long n, m, a[N], dp[N], f[M], inv[M];

long long Pow(int a, int b) {
    if (b == 0)
        return 1;
    long long res = Pow(a, b / 2);
    res = res * res % MOD;
    if (b % 2)
        return res * a % MOD;
    return res;
}

int Catalan(int x) { return (Pow(x + 1, MOD - 2) * f[2 * x] % MOD) * (inv[x] * inv[x] % MOD) % MOD; }

int main() {
    // freopen("MINE.inp" , "r" , stdin);
    // freopen("MINE.out" , "w" , stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i < M; i++) f[i] = f[i - 1] * i % MOD;
    inv[M - 1] = Pow(f[M - 1], MOD - 2);
    for (int i = M - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
    if (m == 1e6) {
        cout << Catalan(n);
        return 0;
    }
    for (int i = 1; i <= 2 * n; i++) cin >> a[i];
    dp[0] = 1;
    for (int i = 2; i <= 2 * n; i += 2)
        for (int j = i - 2; j >= 0; j -= 2) {
            if (a[i] - a[j + 1] <= m) {
                dp[i] = (dp[i] + dp[j] * Catalan((i - j - 2) / 2)) % MOD;
            }
        }
    cout << dp[2 * n];
    return 0;
}

hịc hôm nay 30/4 nghỉ lễ mà cũng có người làm bài tập nè giỏi thiệc

[mark123 (Mark)]

em xin thuật toán á chứ code em có rồi nhưng chưa hiểu thuật toán sao á

anh có thể giải thích thuật toán giúp em được không ạ? hoặc em xin tài liệu về dạng bài ntn ạ

[minhtuan_998]

Mấy này của mấy bạn chuyên tin, mình chịu. Nếu học thể loại này thì mình lên hackerrank hoặc leetcode sẽ có các cấp độ được chia rõ, và code rất dễ hiểu vì mấy anh coder làm phần mềm code, không phải mấy anh đội tuyển chuyên tin. Dù không rành nhưng mình biết trong này dùng quy hoạch động

[mark123 (Mark)]

em xem code mà khó hiểu quá, debug cũng kh hiểu luôn