## 报告错误

如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：

- 使用
**CS Club 网站错误**为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com - 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库

## Problem 2. Hoof, Paper, Scissors

### Problem Summary

Hoof Paper Scissors is a game like paper, scissor, stone. In the game, Hoof > Scissors, Scissors > Paper, and Paper > Hoof. The cow Bessie know the sequence of gesture that will be used by Farmer John, but it only can change its gesture for $k$ times, where $k$ is a number that is less than 20.

Given the gesture sequence of farmer John and maximum number of change ($k$) for Bessie, what is the maximum number of games Bessie can win?

### Proposed Solution

We can use the dynamic programming to solve this problem. First, we noticed that three variables are needed to represent a state for Bessie.

- The current gesture Bessie is using
- The number of game Bessie has won
- The number of time that Bessie change its gesture

Therefore, we will build up a 3D array $T$ with size $3\times N \times k$, where $N$ is the number of games Bessie and John will have. $T[0][n][k]$ represent the maximum number of game that Bessie can win when it has “Hoof” at $n$th game and has changed its gesture for $k$ times.

Suppose we have a function `isWin(gesture, n)`

that will return whether Bessie will win. If Bessie wins, return 1; otherwise, return 0. Then we can calculate through the whole table using these equations:

If either $n$ or $k$ is out of bound (not in 3D array $T$, return 0.

After calculating through all the table, we should check all the elements in slice $T[][N][]$. (the maximum win number may not require maximum number of change). The final result will be the maximum value of these $3\times k$ values.

### Time Complexity Analysis

Since we know that $1\leq N\leq 100,000$ and $1\leq k\leq 20$, the 3D array we will construct has a size of $3\times100,000\times20 = 6\times 10^7$. Since we need to calculate through the whole table, our program may require $1\times 10^8$ computational steps and time complexity of $O(kN)$. Since this time complexity is on the edge of TLE, we should use Java to solve this problem.