[USACO17JAN] Hoof, Paper, Scissor G

GitHub跳转原题关系图返回列表

设 dp[i][j][s] 表示前 i 轮、已经换 j 次手势且当前手势为 s 时的最大胜场数。

OJ: luogu

题目 ID: P3609

难度:普及/提高-

标签:动态规划dp状态设计

日期: 2026-06-21 13:27

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结

题意

一共进行 N 轮猜拳，FJ 每轮出的手势已经知道。

Bessie 每一轮也要出一种手势，并且她在整个过程中最多只能更换 K 次手势。

问她最多能赢多少轮。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力搜索，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, k;
int a[MAXN];
int best_ans;

int win_score(int my_gesture, int opp_gesture) {
    if (my_gesture == 0 && opp_gesture == 2) {
        return 1;
    }
    if (my_gesture == 1 && opp_gesture == 0) {
        return 1;
    }
    if (my_gesture == 2 && opp_gesture == 1) {
        return 1;
    }
    return 0;
}

void dfs(int idx, int used_change, int cur_gesture, int win_cnt) {
    if (idx > n) {
        best_ans = max(best_ans, win_cnt);
        return;
    }

    // 这一轮保持当前手势。
    dfs(idx + 1, used_change, cur_gesture, win_cnt + win_score(cur_gesture, a[idx]));

    // 这一轮前切换到另外两种手势。
    if (used_change < k) {
        for (int s = 0; s < 3; s++) {
            if (s == cur_gesture) {
                continue;
            }
            dfs(idx + 1, used_change + 1, s, win_cnt + win_score(s, a[idx]));
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        char ch;
        cin >> ch;
        if (ch == 'H') {
            a[i] = 0;
        }
        else if (ch == 'P') {
            a[i] = 1;
        }
        else {
            a[i] = 2;
        }
    }

    best_ans = 0;
    for (int s = 0; s < 3; s++) {
        dfs(1, 0, s, 0);
    }

    cout << best_ans << '\n';
    return 0;
}

暴力想法是按顺序枚举每一轮出什么手势，并记录一共换了几次。

但真正影响后面的信息只有三件事：

  1. 现在进行到第几轮
  2. 已经换了几次手势
  3. 当前手势是什么

于是定义：

  • dp[i][j][s] 表示前 i 轮结束，已经换了 j 次手势，当前手势是 s 时，最多能赢多少轮

这里 s 只有三种取值：

  • H
  • P
  • S

转移时分两类：

  1. 第 i 轮保持上一次的手势不变
  2. 第 i 轮前从另外两种手势切换到当前手势

转移完以后，再看当前手势能不能赢下这一轮，把贡献加上即可。

DP 转移方程

设 score(s,i) 表示第 i 轮出手势 s 是否能赢。 保持手势：

dp[i][j][s]=max⁡(dp[i][j][s], dp[i−1][j][s]) dp[i][j][s]=\max(dp[i][j][s],\ dp[i-1][j][s])

切换手势：

dp[i][j][s]=max⁡pre≠s(dp[i][j][s], dp[i−1][j−1][pre]) dp[i][j][s]=\max_{pre\ne s}(dp[i][j][s],\ dp[i-1][j-1][pre])

最后统一加上 score(s,i)。

因为状态数是 N * K * 3，所以这个 DP 很轻。

代码

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

const int MAXN = 100005;
const int MAXK = 25;
const int NEG_INF = -0x3f3f3f3f;

int n, k;
int a[MAXN];
int dp[MAXN][MAXK][3];

int win_score(int my_gesture, int opp_gesture) {
    if (my_gesture == 0 && opp_gesture == 2) {
        return 1; // H 胜 S
    }
    if (my_gesture == 1 && opp_gesture == 0) {
        return 1; // P 胜 H
    }
    if (my_gesture == 2 && opp_gesture == 1) {
        return 1; // S 胜 P
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        char ch;
        cin >> ch;
        if (ch == 'H') {
            a[i] = 0;
        }
        else if (ch == 'P') {
            a[i] = 1;
        }
        else {
            a[i] = 2;
        }
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int s = 0; s < 3; s++) {
                dp[i][j][s] = NEG_INF;
            }
        }
    }

    for (int s = 0; s < 3; s++) {
        dp[0][0][s] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int s = 0; s < 3; s++) {
                // 这一轮保持当前手势。
                dp[i][j][s] = max(dp[i][j][s], dp[i - 1][j][s]);

                // 这一轮前从另外两种手势切换过来。
                if (j > 0) {
                    for (int pre = 0; pre < 3; pre++) {
                        if (pre == s) {
                            continue;
                        }
                        dp[i][j][s] = max(dp[i][j][s], dp[i - 1][j - 1][pre]);
                    }
                }

                dp[i][j][s] += win_score(s, a[i]);
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= k; j++) {
        for (int s = 0; s < 3; s++) {
            ans = max(ans, dp[n][j][s]);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

状态数是 O(NK∗3)O(NK*3)，每个状态只枚举常数个来源。

总时间复杂度 O(NK)O(NK)，空间复杂度 O(NK)O(NK)。

总结

这题的关键不是猜拳规则本身，而是把“最多换 K 次手势”转成状态：

  1. 当前轮数
  2. 已用换手次数
  3. 当前手势

这样就能直接做一个标准的三维 DP。