洛谷P3609 [USACO17JAN] Hoof, Paper, Scissor G 题解

题目链接：P3609 [USACO17JAN] Hoof, Paper, Scissor G

题意：

你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

“蹄子，剪刀，布”和“石头，剪刀，布”的规则十分类似，两只奶牛数到三，然后出一个代表蹄子，剪刀或布的手势。蹄子胜过剪刀，剪刀胜过布，布胜过蹄子。特别地，如果两只奶牛的手势相同，则视为平局。

现在 FJ 和 Bassie 要进行 \(N\) 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换 \(K\) 次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

本题与银组同名题目在题意上一致，唯一的差别在于对变手势次数的限制。

输入格式：

第一行输入两个整数 \(N,K\)（\(1 \leq N \leq 10^5\)，\(0 \leq K \leq 20\)）。

接下来 \(N\) 行，每行一个字母，代表 FJ 这一轮出的手势。H 代表蹄子（Hoof），S 代表剪刀（Scissors），P 代表布（Paper）。

输出格式：

输出一个整数，代表 Bassie 在最多变换 \(K\) 次手势的前提下最多赢多少轮。

读前半段还以为是博弈论，搞了半天就是道简单dp。

设 \(f(i,j,k)\) 表示前 \(i\) 次对抗变了 \(j\) 次手势，最后一个手势是 \(k\) 时能赢多少轮 \((k=0,1,2)\)

转移方程： \[ \begin{aligned} f(i,j,0) = a_i + \max\left\{f(i - 1,~j,~0),~f(i - 1,~j - 1,~1),~f(i - 1,~j - 1,~2)\right\} \\[6pt]f(i,j,1) = b_i + \max\left\{f(i - 1,~j,~1), ~f(i - 1,~j - 1,~0),~f(i - 1,~j - 1,~2)\right\} \\[6pt]f(i,j,2) = c_i + \max\left\{f(i - 1,~j,~2), ~f(i - 1,~j - 1,~0),~f(i - 1,~j - 1,~1)\right\} \end{aligned} \] 其中 \(a_i,b_i,c_i\) 分别表示每个位置是否为 \(0,1,2\) （并相对应地出他们的反制）

滚动数组一下就拿了个最优解，大家是有多懒啊（大雾）

时间复杂度 \(\mathcal{O}(nm)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,m,f[25][3]; char t,a[N],b[N],c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> t; a[i] = (t == 'H');
        b[i] = (t == 'S'); c[i] = (t == 'P');
    }
    f[0][0] = a[1]; f[0][1] = b[1]; f[0][2] = c[1];
    for(int i = 2; i <= n; i++)
        for(int j = m; ~j; j--)
        {
            if(j < 1) { f[j][0] += a[i]; f[j][1] += b[i], f[j][2] += c[i]; }
            else
            {
                int tmp[3] = {f[j][0], f[j][1], f[j][2]};
                f[j][0] = a[i] + max({tmp[0], f[j - 1][1], f[j - 1][2]});
                f[j][1] = b[i] + max({tmp[1], f[j - 1][0], f[j - 1][2]});
                f[j][2] = c[i] + max({tmp[2], f[j - 1][0], f[j - 1][1]});
            }
        }
    int res = 0;
    for(int i = 0; i <= m; i++)
        up(res, max({f[i][0], f[i][1], f[i][2]}));
    cout << res << '\n';
    return 0;
}

补充说明一下：

为什么出现了 tmp[3] 数组？

因为滚动数组使我们直接在 \(f\) 上进行修改，而转移方程中需要用到当前的 \(f(i,\star,\star)\) 。
为什么可以直接从 \(i-1\) 转移？

这个可以算是题解区第一个题解的奇妙问题，因为它试图从 \(l < i\) 转移。

仔细观察一下就会发现，这种转移会有很多很多重复的且没意义的地方，就这么简单。
这里的补充说明是给水平较弱的同学解释用的。
另外，别忘了双倍经验嘿嘿！