USACO Gold 2017 January - Hoof, Paper, Scissors

Official Analysis

Solution

The main observation for this problem is to realize that we only need to keep track of the number of games played $i$, the number of times switched so far $j$, and the current gesture $k$ in order to determine the most amount of previous games won for any game $i$.

For every move, either Bessie can switch to either H, P, S or stay on her current gesture. If she changes her gesture, then the next game $i+1$ will have used $j+1$ gestures, which corresponds to the $\texttt{dp}$ state $\texttt{dp}[i+1][j+1][k]$. We can simulate this for all 3 gestures. Then, we just increment $\texttt{dp}[i][j][k]$ if Bessie wins at game $i$ with gesture $k$.

Note that you can just compare the current gesture to H,P,S because there is always exactly one way to win.

Time Complexity: $\mathcal{O}(NK)$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;

#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) begin(x), end(x)