Hướng dẫn giải của Bedao Regular Contest 20 - Olympic 30/4
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nhận thấy rằng có ~3~ bài, mỗi bài có tối đa ~6~ subtask nên tổng số subtask tối đa là ~18~, vì thế bài này có thể được giải bằng phương pháp sinh nhị phân cơ bản. Gọi tổng số subtask là ~S~, ta sẽ tiến hành sinh trên một xâu nhị phân có độ dài ~S~ biểu diễn một cấu hình với ~1~ là có và ~0~ là không chọn subtask đấy. Để kiểm tra tính hợp lệ của cấu hình, đầu tiên với mỗi subtask ~i~ ta lưu một mảng ~pre_i~ gồm các subtask cần làm trước subtask ~i~, sau đó khi duyệt nếu subtask ~i~ được chọn ta sẽ lần lượt duyệt các subtask trong ~pre_i~ đã được chọn hay chưa. Đương nhiên ngoài tính hợp lệ về subtask ra ta cũng cần đảm bảo tổng thời gian của cấu hình là hợp lệ và lấy điểm tối đa của các cấu hình hợp lệ đó. Độ phức tạp của thuật toán đơn giản này là ~\mathcal{O}(2^S \cdot S^2)~.
Ngoài ra ta có thể thực hiện cải tiến nhẹ bằng cách với subtask ~i~, thay vì lưu ~pre_i~ là mảng ta sẽ lưu nó là một cấu hình (mask) đã bật sẵn các subtask cần làm trước và khi duyệt ta chỉ cần kiểm tra điều kiện ~pre_i~ ~\&~ ~mask = pre_i~, từ đó giảm độ phức tạp xuống còn ~\mathcal{O}(2^S \cdot S)~.
#include <iostream> #include <iomanip> #include <vector> using namespace std; int main() { if(fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } int n = 3; int subtasks = 0; vector<int> subtime, subscore, subpre; for(int i = 0; i < n; ++i) { int subs; cin >> subs; for(int j = 0; j < subs; ++j) { int t, s, cnt, mask = 0; cin >> t >> s >> cnt; subtime.push_back(t); subscore.push_back((i ? 7 : 6) * s); while(cnt--) { int x; cin >> x; --x; mask |= (1 << (subtasks + x)); } subpre.push_back(mask); } subtasks += subs; } int score = 0; for(int mask = 0; mask < (1 << subtasks); ++mask) { bool flag = true; int t = 0, s = 0; for(int i = 0; i < subtasks; ++i) { if(mask & (1 << i)) { if((mask & subpre[i]) != subpre[i]) { flag = false; break; } t += subtime[i]; s += subscore[i]; } } if(!flag) continue; if(t <= 180) score = max(score, s); } cout << fixed << setprecision(2) << score / 100.0; }
Bình luận