Solutions of Sake game

Select solution language

Terence Created at 0 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.