题目传送门

在编写代码的时候多写写注释！！
多写十秒钟注释少调试十分钟程序！！

记忆化搜索

/*
problem:[USACO17JAN] Hoof, Paper, Scissor G
URL:https://www.luogu.com.cn/problem/P3609
time:2023-10-03
记忆化搜索
*/
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;

int n, k;
int a[maxn], F[maxn][22][3]; //f[i][j][k] 前 i 轮，变换了 j 次，最后一次出的 k
// 还有一个小技巧，数组名用大写，为了方便需要多次操作的数组元素用小写字母代替

int dfs(int x, int b, int w) { // 第 x 轮，还可以变换 b 次，上一轮出的 w
    if(!x || b < 0) return 0; //边界条件判断
    int &f = F[x][b][w], p = -1; 
    if(f) return f; 
    for(int i = 0; i <= 2; i++) 
        p = max(p, dfs((x - 1), b - (i != w), i)); //向前搜索，计算需不需要消耗次数
    return f = p + (w == a[x]); //返回能否胜利，并且赋值
}

int main() {
    ios::sync_with_stdio(0); // IO 优化
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    string s = "PHS"; //将字符转化为 int，方便操作
    char c;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> c;
        a[i] = s.find(c); //字符串 s 中的字符很少，时间复杂度可以看作常数
    }
    for(int j = 0; j <= 2; j++) ans = max(ans, dfs(n, k, j));
    cout << ans << "\n"; //建议不要使用 endl 容易出锅
    return 0; //华丽收场
}
/*
编程语言
C++14 (GCC 9)
代码长度
1.05KB
用时
415ms
内存
32.14MB
*/

动态规划 + 滚动数组

/*
problem:[USACO17JAN] Hoof, Paper, Scissor G
URL:https://www.luogu.com.cn/problem/P3609
date:2023-10-03
动态规划+滚动数组
*/

#include <iostream>
#include <algorithm>
using namespace std;

int n, k;
int D[2][24][5]; // D[i][j][k] i 作为滚动数组来使用，j 代表换了多少次手势，k 代表上一次出的手势是什么

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    char ch;
    string s = "HPS"; //记录一下，方便 char 转换为 int 
    for(int i = 1; i <= n; i++) {
        cin >> ch; // 0 克制 1，1 克制 2，2 克制 0
        int ci = i % 2, i1 = ci ^ 1;//ci 代表的是数组 D 使用到的层数，而 i1 代表的是上一层
        for(int j = 0; j <= k; j++) {
            for(int q = 0; q <= 2; q++) {
                int q1 = (q + 1) % 3, q2 = (q + 2) % 3, &d = D[ci][j][q];
                //上面那一行 q q1 q2 代表的是 其他可能会出的手势
                if (q1 == (int)s.find(ch))
                    d = max({D[i1][j][q], D[i1][j + 1][q1], D[i1][j + 1][q2]}) + 1; //不要傻乎乎的嵌套 max， 用一个 {} 就足够了
                else //如果输了
                    d = D[i1][j][q];
            }
        }
    }
    int ci = n % 2; //确定现在是哪一层
    cout << max({D[ci][0][0], D[ci][0][1], D[ci][0][2]}); // max 要用 algorithm 头文件
    return 0; //完美收场
}
/*
编程语言
C++14 (GCC 9)
代码长度
1.16KB
用时
266ms
内存
880.00KB
*/

总结

可以很明显的看出来，方法二的内存是远小于方法一的。
在大型考试的时候开很大的内存容易影响老爷机的心情，导致 TLE
所以说如果感觉空间会很大而且担心超时的情况下还是选择滚动数组吧qaq