SPOJ.COM – Thuật toán bài DIEHARD - Die Hard Game
Đề bài:
Trò chơi vô cùng đơn giản. Ban đầu bạn được cho 'H' lượng máu và 'A' lượng giáp. Tại mỗi thời điểm bất kỳ bạn có thể đứng ở 3 nơi - lửa, nước và không khí. Sau mỗi đơn vị thời gian, bạn phải di chuyển vị trí để có thể sống sót. Ví dụ, nếu bạn đang đứng ở lửa thì bạn có thể bạn có thể di chuyển sang nước hoặc không khí.
Nếu như bạn nhảy vào không khí, bạn sẽ được tăng 3 máu và tăng 2 giáp. Nếu bạn nhảy vào nước, bạn sẽ bị giảm 5 máu và 10 giáp. Nếu như bạn nhảy vào lửa, bạn sẽ bị giảm 20 máu và tăng 5 giáp. Nếu máu hoặc giáp của bạn <= 0 thì bạn sẽ chết ngay lập tức.
Hãy tìm thời gian tối đa bạn có thể sống.
Đầu vào:
Dòng đầu tiên của đầu vào là số lượng testcase t. Mỗi testcase sẽ bao gồm 2 số H và A lần lượt là số máu và số giáp ban đầu.
Đầu ra:
Vói mỗi testcase, in ra thời gian tối đa bạn có thể sống.
Chú ý: bạn có thể chọn 1 trong 3 vị trí cho di chuyển đầu tiên.
Ràng buộc:
1 <= t <= 10
1 <= H, A <= 1000
Ví dụ:
Đầu vào:
3
2 10
4 4
20 8
Đầu ra:
1
1
5
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây:http://www.spoj.com/problems/DIEHARD/
Phân tích
-
Theo đầu bài, ta có thể chọn 1 trong 3 vị trí cho lần di chuyển đầu tiên. Mà bạn có thể thấy rằng nếu nhảy vào không khí thì cả máu và giáp đều tăng. Do đó, tôi chọn đứng ở không khí đầu tiên.
-
Vì chỉ có 3 vị trí nước, không khí và lửa nên khi bạn ở một vị trí bất kỳ thì có thể nhảy sang vị trí còn lại. Mà khi nhảy vào không khí, cả máu và giáp đều tăng. Do đó, nếu bạn nhảy theo thứ tự sau đây sẽ có lợi nhất: Không khí - nước - không khí hoặc Không khí - lửa - không khí.
-
Ở bài toán này, tôi sẽ triển khai cách giải bằng đệ quy, sử dụng thuật toán quy hoạch động - Dynamic programming để lưu lại kết quả thời gian sống lớn nhất ứng với giá trị 'H' máu và 'A' giáp ban đầu.
Lời giải
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include <iostream> | |
| using namespace std; | |
| // Phải cho giá trị MAX lớn hơn ràng buộc đề bài | |
| // Vì giá trị máu hoặc giáp có thể tăng lên | |
| const int MAX = 2005; | |
| const int Fire = 1; | |
| const int Water = 2; | |
| const int Air = 3; | |
| int InitH, InitA; // Giá trị máu và giáp ban đầu | |
| int MaxTime[MAX][MAX]; // Mảng lưu giá trị thời gian sống lớn nhất | |
| // ứng với giá trị 'H' máu và 'A' giáp | |
| /* | |
| * Tìm giá trị lớn nhất của 2 số | |
| * @PARAM: a, b : là 2 số đầu vào | |
| * RETURN: số lớn hơn trong 2 số | |
| */ | |
| int Max(int a, int b) | |
| { | |
| if(a > b) return a; | |
| return b; | |
| } | |
| /* | |
| * Tìm thời gian sống lớn nhất với giá trị máu và giáp ban đầu | |
| * @PARAM: health, armor lần lượt là lượng máu và giáp ban đầu | |
| * RETURN: giá trị thời gian sống lớn nhất | |
| */ | |
| int Check(int health, int armor) | |
| { | |
| if(health <= 0 || armor <= 0) return -1; | |
| // Giả sử lúc đầu ta đang đứng ở Air, ta sẽ nhảy lần lượt sang Fire rồi về Air | |
| // Hoặc sang Water rồi về Air. Vì tại Air thì H và A đều tăng. | |
| // Nếu nhảy sang Fire rồi về Air: máu giảm : 3 - 20 = -17 và giáp tăng: 2 + 5 = 7 | |
| // Nếu nhảy sang Water rồi về Air: máu giảm: 3 - 5 = -2 và giáp giảm: -10 + 2 = -8 | |
| if(MaxTime[health][armor] == -1) | |
| MaxTime[health][armor] = | |
| Max(Check(health - 17, armor + 7) + 2, Check(health - 2, armor - 8) + 2); | |
| return MaxTime[health][armor]; | |
| } | |
| int main(int argc, char** argv) | |
| { | |
| int T, test_case; | |
| ios::sync_with_stdio(false); | |
| //freopen("input.txt", "r", stdin); | |
| for(int i = 0; i < MAX; i++) | |
| for(int j = 0; j < MAX; j++) | |
| MaxTime[i][j] = -1; | |
| cin >> T; | |
| for(test_case = 0; test_case < T; test_case++) | |
| { | |
| // Nhập đầu vào | |
| cin >> InitH >> InitA; | |
| // In kết quả | |
| cout << Check(InitH, InitA) << endl; | |
| } | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.