Solutions of Sake game

Select solution language

Terence Created at 10 likes

Để giải được bài toán trên, ta sẽ sử dụng kĩ thuật Quy hoạch động (DP) nhằm xử lí các trường hợp có thể xảy ra khi còn i cốc rượu. Gọi f[i] là kết quả của trò chơi khi còn i cốc rượu. - Nếu f[i] == true: người chơi đến lượt ở trạng thái này sẽ thắng nếu chơi tối ưu. - Nếu f[i] == false: người chơi đến lượt ở trạng thái này sẽ thua (dù chơi tốt đến đâu). Ban đầu, nếu không còn cốc rượu nào (i = 0) thì rõ ràng là thua → f[0] = false. Với mỗi số cốc rượu i từ 1 đến n: - Ta duyệt tất cả giá trị x trong mảng A. - Nếu có giá trị x sao cho i - x >= 0 và f[i] == false, nghĩa là người chơi có thể đưa đối thủ vào một trạng thái thua, thì trạng thái hiện tại là trạng thái thắng → f[i] = true. Sau khi tính xong f[n], nếu f[n] == true thì người chơi đầu tiên (Marisa) có thể đảm bảo thắng. Ngược lại, nếu f[n] == false, thì Marisa không thể thắng nếu Reimu chơi tối ưu.