【luogu P3609 [USACO17JAN]Hoof, Paper, Scissor蹄子剪刀布】题解

男娘i 2021-12-09 04:15 165阅读 0赞

题目链接：[https://www.luogu.org/problemnew/show/P3609][https_www.luogu.org_problemnew_show_P3609]

## \#\#\# 看着标签什么记搜什么暴力点进来，读完题第一直觉DP？ ##

还真是个\\(DP\\)。

题目所描述的状态十分明显，第 \\(i\\) 轮，变换 \\(j\\) 次，当前FJ手势 (\\(x,y,z\\))

那我们不妨直接令\\(f\[i\]\[j\]\[k\]\\)表示当前第 \\(i\\) 轮，变换 \\(j\\) 次，在FJ手势为 \\(k\\) 时的胜场为多少。（这里懒得考虑啥手势能胜FJ，故直接用FJ的手势为参考。）

那么在转移时，我们考虑的就是两种情况：

要么我换个手势赢FJ的当前手势，要么我不换手势。

#### 对于换手势： ####

如果变换到\\(x\\)手势赢FJ：

\\(f\[i\]\[j\]\[x\] = max(f\[i-1\]\[j-1\]\[y\], f\[i-1\]\[j-1\]\[z\]) + num\[i\]\[x\]\\)

其中，num\[i\]\[x\]代表我当前是否能赢FJ的x手势，1为能赢，0为不能赢。

对于变换到y,z手势同理。

#### 对于不换手势： ####

\\(f\[i\]\[j\]\[x\] = f\[i-1\]\[j\]\[x\] + num\[i\]\[x\]\\)

所以总转移方程为：

\\(f\[i\]\[j\]\[x\] = max(max(f\[i-1\]\[j-1\]\[y\], f\[i-1\]\[j-1\]\[z\]) + num\[i\]\[x\], f\[i-1\]\[j\]\[x\] + num\[i\]\[x\])\\)

接下来就是O(NK)的转移，最后在第n轮中变换0~k次的三个不同手势中选出max即为答案。

### code： ###

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn = 1e5 + 10;
    int f[maxn][21][3], k, n, answer;
    int num[maxn][3];//H 0  P 1  S 2
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i++)
        {
            char s;
            cin>>s;
            if(s == 'H')
            num[i][0] = 1;
            if(s == 'P')
            num[i][1] = 1;
            if(s == 'S')
            num[i][2] = 1;
        }
        
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= k; j++)
            {
                if(j - 1 >= 0)//避免数组下标j-1越界
                {
                    f[i][j][0] = max(max(f[i-1][j-1][1], f[i-1][j-1][2]) + num[i][0], f[i-1][j][0] + num[i][0]);
                    f[i][j][2] = max(max(f[i-1][j-1][1], f[i-1][j-1][0]) + num[i][2], f[i-1][j][2] + num[i][2]);
                    f[i][j][1] = max(max(f[i-1][j-1][0], f[i-1][j-1][2]) + num[i][1], f[i-1][j][1] + num[i][1]);
                }
                else
                {
                    f[i][j][0] = f[i-1][j][0] + num[i][0];
                    f[i][j][2] = f[i-1][j][2] + num[i][2];
                    f[i][j][1] = f[i-1][j][1] + num[i][1];    
                }
            }
            for(int j = 0; j <= k; j++)
            {
                answer = max(answer, f[n][j][0]);
                answer = max(answer, f[n][j][1]);
                answer = max(answer, f[n][j][2]);
            }
        printf("%d",answer);    
        return 0;
    }

#### 后记： ####

一开始我交的WA了两次，原因是当j=0时j-1的数组下标导致越界。学校机房自测无误，到luogu上交出毛病来了，总觉得自己机子没有报错就无所谓，下次还需注意改掉这个毛病。（辣鸡dev）

转载于:https://www.cnblogs.com/MisakaAzusa/p/11012878.html

[https_www.luogu.org_problemnew_show_P3609]: https://www.luogu.org/problemnew/show/P3609