标签：AtCoder int 题解 高桥 Janken max 局出 青木

D - AtCoder Janken 3题解

题意

高桥和青木要玩石头剪刀布，给你一个长度为 \(n\) 的字符串 \(s\)，\(s\) 表示青木在第 \(i\) 局游戏中的动作（R 表示石头，P 表示布，S 表示剪刀）。

高桥不可以在任何一局中输给青木（即：高桥和青木只可以平局或高桥赢青木），且高桥第 \(i\) 局出的和第 \(i-1\) 局出的不能一样，现在，问你高桥可以胜几局？

解题思路

很明显是一道 DP 题。

定义状态

\(f_{i,j}\) 表示第 \(i\) 局出 \(j\) 时最多可以获胜的局数（\(j = 1\) 时表示出石头，\(j = 2\) 时表示出布，\(j = 3\) 时表示出剪刀）。

初始化：

if (s[0] == 'R') {
        f[0][1] = 0; // 两人一起出石头，不计分
        f[0][2] = 1; // 高桥出布，高桥加一分
        // 注意：高桥不可以输给青木，所以 f[0][3] 不可以初始化为 -1
    }
    if (s[0] == 'P') {
        f[0][2] = 0; // 同理
        f[0][3] = 1;
    }
    if (s[0] == 'S') {
        f[0][1] = 1;
        f[0][3] = 0;
}

转移方程：

当 \(s_i =\textrm{R}\) 时：

\[f_{i,1} = \max(f_{i-1,2}, f_{i-1,3})\\ f_{i,2} = \max(f_{i-1,1}, f_{i-1,3}) + 1 \]

（注意：\(f_{i,1}\) 是被 \(f_{i-1,2}\) 和 \(f_{i-1,3}\) 转移过来的，因为高桥第 \(i\) 局出的和第 \(i-1\) 局出的不能一样，
高桥不可以输给青木，所以 \(j\) 不可以取 \(3\)，即：不可以出剪刀）。
当 \(s_i =\textrm{P}\) 时：

\[f_{i,2} = \max(f_{i-1,1}, f_{i-1,3})\\ f_{i,3} = \max(f_{i-1,2}, f_{i-1,3}) + 1 \]

当 \(s_i =\textrm{S}\) 时：

\[f_{i,1} = \max(f_{i-1,2}, f_{i-1,3}) + 1\\ f_{i,3} = \max(f_{i-1,1}, f_{i-1,2}) \]

答案就取 \(\max(f_{n - 1,1},f_{n - 1,2},f_{n - 1,3})\)，（我的字符串 \(s\) 下标从 \(0\) 开始存）。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, ans, f[N][10];
string s;
main() {
    cin >> n >> s;
    if (s[0] == 'R') {
        f[0][1] = 0;
        f[0][2] = 1;
    }
    if (s[0] == 'P') {
        f[0][2] = 0;
        f[0][3] = 1;
    }
    if (s[0] == 'S') {
        f[0][1] = 1;
        f[0][3] = 0;
    }
    for (int i = 1; i < n; i++) {
        if (s[i] == 'R') {
            f[i][1] = max(f[i - 1][2], f[i - 1][3]);
            f[i][2] = max(f[i - 1][1], f[i - 1][3]) + 1;
        }
        if (s[i] == 'P') {
            f[i][2] = max(f[i - 1][1], f[i - 1][3]);
            f[i][3] = max(f[i - 1][1], f[i - 1][2]) + 1;
        }
        if (s[i] == 'S') {
            f[i][1] = max(f[i - 1][2], f[i - 1][3]) + 1;
            f[i][3] = max(f[i - 1][1], f[i - 1][2]);
        }
    }
    cout << max({f[n - 1][1], f[n - 1][2], f[n - 1][3]});
    return 0;
}

标签：AtCoder,int,题解,高桥,Janken,max,局出,青木
From： https://www.cnblogs.com/ACyming/p/18361929