Hướng giải: Oẳn tù tì

Nguồn: USACO

Vì Bessie chỉ có thể sử dụng một ký hiệu duy nhất trong mỗi đoạn, nên trong một đoạn, chiến lược tốt nhất là chọn ký hiệu để đối đầu với ký hiệu mà Farmer John sử dụng nhiều nhất trong đoạn đó. Do đó, số ván thắng tối đa trong một đoạn chính là số lượng ký hiệu ~\text{H}~, ~\text{P}~ hoặc ~\text{S}~ xuất hiện nhiều nhất trong đoạn.

Ta có thể tính trước số lượng ~\text{H}~, ~\text{P}~ và ~\text{S}~ tại mỗi vị trí bằng tổng tiền tố (prefix sum). Sau đó, với mỗi điểm chuyển có thể có, ta tính số ván thắng tối đa ở đoạn trước và đoạn sau, cộng hai giá trị này lại và tìm ra giá trị lớn nhất.