G Haitang and Rock Paper Scissors 题解

在竞赛讨论区看 Latex一切正常。

首先考虑朴素dp，

定义 为前 个对手中，在第 个对手出石头/步/剪刀能得到的最大分数为 的方案数。

那么我们最终的答案就是 。

对于状态方程，当前为 ，然后前一个石头/布/剪刀能得到的最大分数为 。

对手出的石头，那么状态方程为 。

对手出的布，那么状态方程为 。

对手出的剪刀，那么状态方程为 。

当我们本轮出石头，那我们对前一轮的布和剪刀取 ，这样一定可以避免连续两轮出一样的手势。

这样的时间复杂度是 的。

我们考虑如何优化，这里我们可以通过转移方程看到，一定有一维是 ，那么我们可以用一个手势来代替这一维。

定义 为前 个对手中，在第 个对手出 能得到的最大分数为 的方案数。

那么答案还是同理 。

对于状态方程，当前为 ，然后前一个 能得到的最大分数为 ，

对手出的 ，那么我们需要考虑 和 的关系。

我们这一轮为 的手势是 ，所以我们第四维一定是 。

所以我们 ， 表示取 和 得分的最大值， 表示取 和 得分的最大值 。

定义 。

对于第 轮， 的最大得分为 ， 的最大得分为 。

当 时，

• 此时 。
• 表示取 和 得分的最大值，这里为 。
• 表示取 和 得分的最大值 ，这里为 ，因为 是 。
• 所以状态转移方程为 。

当 时，

• 此时 。
• 表示取 和 得分的最大值，这里为 ，因为 是 。
• 表示取 和 得分的最大值 ，这里为 ，因为 是 。
• 所以状态转移方程为 。

当 时，

• 此时 。
• 表示取 和 得分的最大值，这里为 ，因为 是 。
• 表示取 和 得分的最大值 ，这里为 。
• 所以状态转移方程为 。

到这里时间复杂度优化为 。

我们还需要优化时间复杂度。

这里我们可以想到我们无论如何都不可能失败，总可以做到要么赢，要么平局。

那么从这一点，我们的 是一定不会减少的。

所以一但 增加，我们之后的所有方案都不会减少了，而且一但增加，只会增加 ，

那么从这一步开始有多少方案，我们就贡献了 乘上方案个数。

对于某一段的方案数，假设这一段的 的数量为 ，那么这一段的方案数为 。

所以我们需要维护一个 数量的前缀和。

定义 表示第 个到第 个之间有多少个 。

既然只需要 ，我们可以直接维护 ，这样 也可以同时维护。

定义 为前 个对手中，在第 个对手出 能得到的最大分数减去 能得到的最大分数为 的方案数。

对手出的 ，我们还是要考虑 和 的关系。

我们这一轮为 的手势是 ，所以我们第三维一定是 。

所以我们 ， 表示取 和 得分的最大值， 表示取 和 得分的最大值 。

定义 。

对于第 轮， 的最大得分为 ， 的最大得分为 ，。

当 时，

• 此时 。

• 表示取 和 得分的最大值，这里为 。

• 表示取 和 得分的最大值 ，这里为 ，因为 是 。

• 那么 ，

• 这个式子我们可以轻易的看出当 即 ，得到 。

• 否则得到 。

• 所以状态转移方程为

• 当 时，，

• 否则，。

• 然后 ，

• 此时当 最大值才会变化，也就是说 ，

• 这个式子等价于 。

• 所以当 的时候，我们对答案的贡献为 。

当 时，

• 此时 。

• 表示取 和 得分的最大值，这里为 ，因为 是 。

• 表示取 和 得分的最大值 ，这里为 ，因为 是 。

• 那么 ，

• 所以状态转移方程为

• 

• 然后

• 此时只有 最大值才会变化，也就是说 ，

• 这个式子等价于 。

• 所以当 的时候，我们对答案的贡献为 。

当 时，

• 此时 。
• 表示取 和 得分的最大值，这里为 ，因为 是 。
• 表示取 和 得分的最大值 ，这里为 。
• 那么 ，
• 此时当 即 ，得到 ，
• 否则得到 。
• 所以状态转移方程为
• 当 ，，
• 否则，。
• 然后 ，
• 此时无论何时都会发现 都会变大，
• 这个时候直接对答案贡献为 。

最终时间复杂度为 。