P3609 [USACO17JAN]Hoof, Paper, Scissor蹄子剪刀…

    • 114通过
    • 290提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 搜索 模拟 记忆化搜索 USACO 2017 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    欢迎提供翻译,请直接在讨论区发帖,感谢你的贡献。

    题目描述

    You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors".

    The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each simultaneously makes a gesture that represents either a hoof, a piece of paper, or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors beats paper (since scissors can cut paper), and paper beats hoof (since the hoof can get a papercut). For example, if the first cow makes a "hoof" gesture and the second a "paper" gesture, then the second cow wins. Of course, it is also possible to tie, if both cows make the same gesture.

    Farmer John wants to play against his prize cow, Bessie, at $N$ games of "Hoof, Paper, Scissors" ( $1 \leq N \leq 100,000$ ). Bessie, being an expert at the game, can predict each of FJ's gestures before he makes it. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same gesture multiple times in a row. In fact, she is only willing to switch gestures at most $K$ times over the entire set of games ( $0 \leq K \leq 20$ ). For example, if $K=2$ , she might play "hoof" for the first few games, then switch to "paper" for a while, then finish the remaining games playing "hoof".

    Given the sequence of gestures FJ will be playing, please determine the maximum number of games that Bessie can win.

    你可能听说过“石头,剪刀,布”的游戏。FJ的牛喜欢玩一个类似的游戏,它们称之为“蹄子,剪刀,布”(“蹄子”就是“石头”)。

    游戏规则很简单:比赛双方同时数到3,然后同时出一个手势,代表“蹄子”“剪刀”或“布”。“蹄子”胜“剪刀”,“剪刀”胜“布”,“布”胜“蹄子”。举个例子,第一头牛出“蹄子”,第二头牛出“布”,则第二头牛胜利。当然,也可以“平局”(如果两头牛手势相同的话)。

    FJ想对阵自己获奖的牛,贝西。贝西作为一个专家,能够预测FJ的手势。不幸的是,贝西作为一头牛,也十分的懒惰。事实上,她只愿意变换固定次数的手势来完成游戏。例如,她可能只想变1次,则他可能出“蹄子”几次,剩下的都出“布”。

    鉴于贝西预测FJ会出的手势,以及她想变的次数,求出她最多能赢多少场

    输入输出格式

    输入格式:

    The first line of the input file contains $N$ and $K$ .

    The remaining $N$ lines contains FJ's gestures, each either H, P, or S.

    输出格式:

    Print the maximum number of games Bessie can win, given that she can only change gestures at most $K$ times.

    输入输出样例

    输入样例#1: 复制
    5 1
    P
    P
    H
    P
    S
    输出样例#1: 复制
    4
    

    说明

    感谢 @lzyzz250 的翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。