Công ty xây dựng SVI phải lựa chọn các dự án cần thực hiện để lợi nhuận đem lại là nhiều nhất. Công ty có một danh sách gồm dự án đánh số từ đến . Sau khi công ty rà soát năng lực thực hiện các dự án, công ty đưa ra bảng đánh giá hiệu quả (có thể là lợi nhuận, có thể là thua lỗ) từ việc thực hiện dự án là (nếu thì đó là lợi nhuận đem lại, còn thì đó là thua lỗ phải chịu từ việc thực hiện dự án , ). Việc lựa chọn các dự án cần thực hiện để lợi nhuận đem lại là lớn nhất không phải là đơn giản bởi vì công ty không thể chỉ lựa chọn các công việc đem lại lợi nhuận để thực hiện. Có một danh sách gồm điều kiện liên quan đến việc lựa chọn thực hiện các dự án. Điều kiện thứ yêu cầu: “Nếu thực hiện dự án thì phải thực hiện dự án ”, . Một tập con các dự án được gọi là lựa chọn được nếu mỗi dự án trong nó luôn thỏa mãn các điều kiện nêu trong danh sách.
Yêu cầu: Hãy giúp công ty tìm tập các dự án lựa chọn được mà việc thực hiện chúng đem lại tổng hiệu quả lớn nhất.
Dữ liệu:
Dòng đầu ghi một số nguyên dương ;
Dòng thứ hai ghi số nguyên tương ứng là tính hiệu quả của từng dự án;
Dòng thứ ba ghi một số nguyên dương ;
Dòng thứ trong số dòng tiếp theo ghi hai số nguyên dương và chỉ sự ràng buộc nếu thực hiện dự án thì phải thực hiện dự án .
Kết quả:
Ghi ra duy nhất một số nguyên là tổng hiệu quả của tập các dự án cần thực hiện tìm được. Ghi ra số nếu như không chọn dự án nào cả.
Ví dụ:
Dữ liệu:
6
10 4 -5 3 -1 -2
4
2 3
2 5
6 5
4 3
Kết quả:
11
Giải thích:
Tập con các dự án lựa chọn được cần tìm là đem lại tổng hiệu quả là .
Ràng buộc:
Có số test tương ứng với các bộ dữ liệu có giới hạn ;
Có số test khác tương ứng với các bộ dữ liệu có giới hạn .
Có số test còn lại tương ứng với các bộ dữ liệu có giới hạn .
