Chuỗi dự án (PROJECTS)
Có dự án có sẵn cho bạn. Đối với mỗi dự án, bạn biết ngày bắt đầu, ngày kết thúc và tiền thưởng nhận được khi hoàn thành. Bạn chỉ có thể làm việc trên một dự án tại một thời điểm. Hai dự án và được coi là không giao nhau nếu hoặc .
Yêu cầu: Hãy chọn một tập hợp con các dự án không giao nhau sao cho tổng tiền thưởng bạn nhận được là lớn nhất.
Dữ liệu:
- Dòng đầu tiên chứa một số nguyên : số lượng dự án.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên : ngày bắt đầu, ngày kết thúc và tiền thưởng của dự án thứ .
Kết quả: In ra tổng tiền thưởng tối đa có thể đạt được.
Ví dụ:
Dữ liệu:
4
2 4 4
3 6 6
6 8 2
5 7 3
Kết quả:
7
Giải thích: Bạn có thể chọn dự án đầu tiên ( thưởng 4) và dự án thứ tư ( thưởng 3), tổng thưởng là 7. Đây là lựa chọn tối ưu.
Giới hạn: , , .
Yêu cầu: Code sau chưa đúng, hãy chỉ ra lỗi sai và tạo ra một testcase mà code này cho kết quả sai.
Testcase gồm 2 file:
PROJECTS.INP: là dữ liệu vào.
PROJECTS.OUT là kết quả đúng.
Code C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Cấu trúc lưu thông tin dự án
struct Project {
long long start, end, profit;
};
// Hàm so sánh để sắp xếp theo thời gian kết thúc
bool compareProjects(const Project& a, const Project& b) {
return a.end < b.end;
}
int main() {
// Tối ưu nhập xuất
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
vector<Project> projects(n);
for (int i = 0; i < n; ++i) {
cin >> projects[i].start >> projects[i].end >> projects[i].profit;
}
// Sắp xếp các dự án theo thời gian kết thúc
sort(projects.begin(), projects.end(), compareProjects);
// Mảng lưu thời gian kết thúc để tìm kiếm nhị phân
vector<long long> end_times;
for (const auto& p : projects) {
end_times.push_back(p.end);
}
// dp[i] là lợi nhuận tối đa khi xét i dự án đầu tiên
// dp[0] = 0
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
long long current_profit = projects[i-1].profit;
long long current_start = projects[i-1].start;
// Tìm dự án cuối cùng có thời gian kết thúc < current_start
// lower_bound trả về phần tử đầu tiên >= current_start
// Do đó phần tử đứng ngay trước nó sẽ < current_start
auto it = lower_bound(end_times.begin(), end_times.end(), current_start);
int idx = distance(end_times.begin(), it);
// Nếu tìm thấy dự án tương thích trước đó
if (idx > 0) {
current_profit += dp[idx];
}
// Công thức DP: Chọn max giữa việc (không chọn dự án này) và (chọn dự án này + dp trước đó)
dp[i] = max((long long)dp[i-1], current_profit);
}
cout << dp[n] << endl;
return 0;
}