Thu hoạch chanh
Xem PDF
Kaninho trồng \(n\) cây chanh và được đánh số từ \(1\) đến \(n\).
Cây chanh thứ \(i\) ra \(b_i\) quả chanh và sẽ được Kaninho thu hoạch vào ngày thứ \(a_{i}\). Nhưng không may mắn thay, nếu không thu hoạch đúng thời điểm, chanh trên cây sẽ bị sâu đục và sẽ không thể ăn được nữa, do đó Kaninho quyết định sẽ thu hoạch nó vào ngày thứ \(a_i\) hoặc \(a_{i}+1\) (tất cả những trái chanh không được thu hoạch vào hai ngày này sẽ bị hư).
Mặc dù bận trăm công nghìn việc nhưng anh ấy vẫn dành ra thời gian mỗi ngày để đem giỏ ra vườn và thu hoạch chanh. Vì chiếc giỏ này chỉ có khả năng chứa được tối đa \(v\) quả nên mỗi ngày, anh ấy cũng chỉ có thể thu được tối đa \(v\) quả mà thôi, biết rằng, mỗi ngày, anh ấy có thể thu hoạch chanh ở cùng một cây hoặc những cây chanh khác nhau. Hỏi sau tất cả, anh ấy có thể thu được tối đa bao nhiêu quả chanh ?
Input
-
Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase
-
\(t\) block tiếp theo, mỗi block có dạng như sau:
-
Dòng thứ nhất chứa hai số nguyên \(n,v(1\le n,v\le 3000)\)
-
\(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i,b_i(1\le a_i,b_i\le 3000 )\)
Output
- Ứng với mỗi testcase, in ra đáp án cần tìm
Example
Test 1
Input
7
7 6
2 2
3 2
4 2
2 4
2 4
5 2
3 3
6 5
5 2
3 3
5 4
5 5
3 4
2 2
10 8
3 4
4 2
2 3
5 5
2 5
4 4
2 2
3 2
2 3
2 5
7 9
3 2
3 4
3 2
2 5
3 2
5 2
4 3
6 6
2 2
3 2
2 4
5 3
3 2
2 4
5 6
5 3
3 5
3 4
5 5
3 4
9 8
3 5
4 5
5 4
4 4
5 5
2 5
4 5
4 3
4 2Output
19
19
33
20
17
20
34
Bình luận
Editioral(mong admin add editioral của em ạ)
Author: huyhau6a2
\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)
\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\color{orange}{\text{Hướng dẫn}}\)
Nhận xét: Các bạn thực chất không cần quan tâm các giá trị \(a_i, b_i\) mà chỉ cần quan tâm, vào ngày thứ \(j\), có bao nhiêu quả chanh đã ra quả mà thôi!
\(\color{goldenrod}{\text{Tiếp cận}}\)
Đầu tiên, ta gọi mảng \(P\) chỉ số quả đã ra quả trong ngày thứ \(i\)
Sau đó, các bạn sẽ thực hiện như sau:
Các bạn cần phải hiểu là cách thu hoạch tối ưu nhất là phải quan tâm thu hoạch chanh vào ngày \(i-1\) sau đó mới thu hoạch vào ngày \(i\)
Vì \(a_i\) trong đoạn \(3000\) nên các bạn cần lặp tối đa \(3001\) lần
Mỗi lần, các bạn gọi biến \(p\) là số chanh trong ngày trước, \(r\) là số chanh trong ngày hôm nay, số chanh thu hoạch trong ngày đó sẽ bằng \(min(k,p+r)\)
Cuối cùng, các bạn cập nhật biến \(p\) thành số chanh còn lại sau khi thu hoạch ngày đó là xong(ở đây mình chỉ tính ngày \(i\), ngày \(i-1\) coi như bỏ qua vì ngày hôm sau chanh ngày \(i-1\) sẽ không thu hoạch được nữa)
\(\color{purple}{\text{Độ phức tạp}}\)
Các bạn có thể làm trong \(O(n+3001)\) hoặc tối ưu hơn!
1 bình luận nữa