Catch Fish

View as PDF

Submit solution


Points: 0.46 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
COI 03
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hồi nhỏ, Mirko thích chơi "Bắn tàu" nhưng bây giờ anh ta chơi trò "Câu cá trên sông" "Sea battle".

Trò chơi mô tả trên ~1~ bảng ~N~ ô đánh số từ ~1~ đến ~N~ từ trái qua phải. Trên đó sẽ đặt ~M~ tàu. Với mỗi ô sẽ biết số lượng cá mà ở trong ô đó. Mỗi tàu sẽ chiếm ~1~ số ô liên tiếp và nó phải thả neo vào ~1~ ô nào đó. Nghĩa là ta sẽ biết được với mỗi tàu, ô mà tàu đó bắt buộc phải chiếm.

Chỉ có thể có ~1~ tàu trên mỗi một ô. Lượng cá bắt được là tổng lượng cá nằm trong ô mà tàu này chiếm. Cần bắt được nhiều cá nhất.

Bạn hãy giúp Mirko đặt tàu.

Input

Dòng đầu là số ~N~, số ô, ~1 \leq N \leq~ ~100000~.

Dòng tiếp theo là ~N~ số nguyên mô tả khối lượng cá trong từng ô, mỗi số ~\geq 1~ và ~\le~ ~100~.

Dòng tiếp theo là số tàu ~M~, ~1 \leq M \leq N~.

~M~ dòng tiếp theo, mỗi dòng gồm ~2~ số ~B~ và ~D~, nghĩa là tàu phải thả neo ở ô ~B~ và tàu có độ dài là ~D~ ô.

Output

Khối lượng cá lớn nhất bắt được.

Sample Input 1

11
2 5 3 4 7 6 2 1 3 8 5
2
8 3
3 2

Sample Output 1

20

Sample Input 2

13
3 2 4 7 2 1 3 6 1 2 6 4 1
2
5 7
11 4

Sample Output 2

38

Sample Input 3

11
1 1 6 4 4 1 1 3 10 1 1
3
2 3
6 4
10 2

Sample Output 3

31

Comments

Please read the guidelines before commenting.



  • 0
    K32NGHIEMDUNG  commented on Oct. 30, 2024, 11:02 p.m.

    Có thể nói, đây là một bài toán hay và độc đáo.

    Trước hết ta hãy cùng đi qua về Input/Output mẫu để hiểu rõ đề bài.

    SAMPLE INPUT 1

    11
    2 5 3 4 7 6 2 1 3 8 5
    2
    8 3
    3 2
    

    SAMPLE OUTPUT 1

    20
    

    Dễ dàng thấy được thì với con tàu thứ nhất, nó sẽ nằm ở vị trí 8-9-10 và 2-3 tương ứng với con tàu thứ hai. Khi đó ta sẽ thu về khối lượng cá mong muốn là ~1+3+8+5+3=20~.

    Ta có thể nhận ra, đây là một bài toán quy hoạch động.

    HƯỚNG GIẢI

    Quy ước: tàu hướng về phía bên phải (->) nên tạm coi tàu có dạng <đuôi tàu>XXX<đầu tàu>

    Ta sẽ gọi mảng ~dp_i~ với ý nghĩa là khối lượng cá nhiều nhất bắt được khi xét tới ô thứ ~i~. Như vậy kết quả của bài toán sẽ là ~dp_n~.

    Khi ấy ta sẽ có các trường hợp:

    • Nếu tàu đang xét hiện tại không thể vươn tới ô thứ ~i~, thì khối lượng cá thu được không thay đổi: ~dp_i=dp_{i -1}~.
    • Nếu có thể thì ta sẽ xét xem với đầu tàu đặt tại ô thứ ~i~ thì có bị vướng vào neo của thuyền trước đó hay không.
      • Nếu thỏa mãn thì thử nếu đặt tàu sao cho đầu tàu tại ô thứ ~i~ có đạt giá trị lớn nhất hay không: ~dp_i=max(dp_i, dp_{i-d_i} + sum(i-d_i, i))~.

    Để giải bài toán dễ dàng, nhanh chóng hơn, ta có thể:

    • Sắp xếp lại mảng lưu thông tin của các con tàu theo vị trí đặt neo rồi dùng một biến ~cur~ nào đó để trỏ tới con tàu đang xét hiện tại.
    • Để tính ~sum()~ ta có thể dùng tổng tiền tố.

    Nếu bạn tinh ý đá gợi ý này và lời giải thì có thể nhận ra gợi ý tôi đang viết có vẻ khá giống cách làm của anh hieult. Nên bạn có thể dùng gợi ý này để hiểu code của anh ấy hơn. (Em cũng đá lời giải nên mới code được và muốn viết lại lời giải ở đây để sau không hiểu thì đọc =/)

    Cảm ơn bầu Đức mọi người.

    From GieJack™ with love <3