Hướng giải của Cây game - Minimax cơ bản
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải
Phân tích
Bài toán yêu cầu tính giá trị Minimax trên cây game. Ở mỗi nút trong, người chơi hiện tại sẽ chọn nút con có lợi nhất cho mình:
- Nếu là lượt MAX (An, độ sâu chẵn), chọn giá trị lớn nhất trong các con.
- Nếu là lượt MIN (Bình, độ sâu lẻ), chọn giá trị nhỏ nhất trong các con.
Ta có thể cài đặt đệ quy Minimax. Với \(N \le 50\), độ phức tạp \(O(N)\) là đủ.
Có thể áp dụng cắt tỉa Alpha-Beta để tối ưu, nhưng với giới hạn nhỏ, Minimax thường là đủ.
Mã nguồn C++
// Giải thuật ab cho bài toán ab-minimax-basic\n#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
vector<vector<int>> adj;
vector<long long> val;
long long dfs(int u, bool maximizing) {
if (adj[u].empty()) return val[u];
long long best = maximizing ? -INF : INF;
for (int v : adj[u]) {
long long cur = dfs(v, !maximizing);
if (maximizing) best = max(best, cur);
else best = min(best, cur);
}
return best;
}
int main() {
// Doc du lieu dau vao
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
adj.assign(n + 1, {});
val.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
int p; cin >> p;
adj[p].push_back(i);
}
for (int i = 1; i <= n; i++) {
cin >> val[i];
}
cout << dfs(1, true) << "\n";
return 0;
}
Nhận xét