| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P151PROB - ROUND 1B - Rubik đi siêu thị |
Rubik đi siêu thị mua n món đồ và để vào trong xe đẩy rồi mang ra quầy thanh toán. Biết mặt hàng thứ i có giá là C_i và người thu ngân cần thời gian T_i để có thể xác nhận mặt hàng này. Nhưng Rubik là thánh ăn trộm nên anh ta đã sắp xếp thứ tự các mặt hàng cho người thu ngân xác nhận theo ý của mình, khi người thu ngân bận làm thủ tục là Rubik sẽ có thể ăn trộm 1 món đồ từ chính xe của mình và mất 1 giây.
Bạn hãy tính xem số tiền tối thiểu mà Rubik phải trả là bao nhiêu?
Input
Dòng đầu tiên chứa số mặt hàng n ( 1 <= n <= 2000).
Sau đó n dòng là cặp T_i và C_i tương ứng là thời gian xác nhận và giá tiền của mặt hàng thứ i (0 <= T_i <= 2000, 1 <= C_i <= 10^9 ). Nếu T_i bằng 0 thì Rubik không thể trộm thứ gì khi nhân viên xác nhận mặt hàng thứ i.
Output
Dòng duy nhất chứa số tiền ít nhất mà Rubik phải trả.
Example
Input:4
2 10
0 20
1 5
1 3 Output: 8
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-04 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2015-05-04 06:39:48 Hiệp
Gọi F là kết quả với F[i] là giá trị nhỏ nhất khi mua được i món hàng. Khi nhập món hàng thứ i thì ta có 2 khả năng: – Chọn món hàng thứ i nhân viên thu ngân kiểm tra, sẽ mất t_i giây và lúc đó sẽ ăn trộm thêm được t_i món hàng, cộng với cả món hàng thứ i thì sẽ có i + t_i + 1 món hàng được lấy bao gồm cả của Rubik và số món hàng để lại thanh toán và ta sẽ có mối liên hệ giữa f[j + t_i + 1] với f[j] với j bất kì. – Món hàng thứ i có thể được ăn trộm từ thời gian của các món hàng trước, trường hợp này đã được xét ở trên với j bất kì. Kết quả bài toán sẽ là f[n] khi cả n món đều đã được lấy hết. |
|
|
2015-05-03 08:36:14 Ngát Taro
Last edit: 2015-05-24 15:18:43 |
