[C++知识库]洛谷 P3069 Hoof Paper Scissor G

原题链接

首先，这道题用记搜就行，甚至都不用STL。

先把数组（我说过不用STL）写上

long long memory[4][21][100001] = {0};

第二，我们要有一个可以判断输赢的函数

bool win(const char &p1, const char &p2){
    return ((p1 == 'H' && p2 == 'S') || (p1 == 'S' && p2 == 'P') || (p1 == 'P' && p2 == 'H'));
}

再就是，如果我们以'H', 'P', 'S'作为索引的话，数组就要大到不可思议，所以我们要把它们转换成0, 1, 2

int change(const char &pose){
    if (pose == 'H'){
        return 0;
    }
    else if (pose == 'P'){
        return 1;
    }
    else{
        return 2;
    }
}

主要的函数HPS（随便起了个名）。

身为一个高等动物，既然知道了FJ接下来的手势，我们在下一步就有变手和不变手两种选择。
但这时，身为一个灵长类的高等动物，我们一定不会为了输而变手。
当然，也有可能下一步不变手才是正确选择。
这样，在k>0的时候，我们有如下的代码

	bool flag = win(pose, Fj[i]);
    if (k > 0){
        switch (Fj[i + 1]){
        case 'H':
            if (pose == 'P'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('P', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }

        case 'S':
            if (pose == 'H'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('H', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }

        case 'P':
            if (pose == 'S'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('S', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }
        }
    }

但是，如果k == 0 了，我们只有不变手一种选择：

else{                                                    // k == 0
        memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
        return memory[change(pose)][k][i];
    }

另外，还有递归的出口（方便起见，我们将n作为全局变量）

	if (memory[change(pose)][k][i]){
        return memory[change(pose)][k][i];
    }
    if (i > n){
        return 0;
    }

封装一下：

int hps(char pose, int k, int i = 0){
    if (memory[change(pose)][k][i]){
        return memory[change(pose)][k][i];
    }
    if (i > n){
        return 0;
    }
    bool flag = win(pose, Fj[i]);
    if (k > 0){
        switch (Fj[i + 1]){
        case 'H':
            if (pose == 'P'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('P', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }

        case 'S':
            if (pose == 'H'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('H', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }

        case 'P':
            if (pose == 'S'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('S', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }
        }
    }
    else{
        memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
        return memory[change(pose)][k][i];
    }
    return 0;
}

主函数

简单至极（原核生物的水平）

int main(){
    int k;
    cin >> n >> k;                                                           //我说过n是全局变量
    for (int i = 0; i < n; i++){
        cin >> Fj[i];
    }
    cout << max({hps('S', k), hps('P', k), hps('H', k)});
    return 0;
}

AC代码

#include<bits/stdc++.h>

using namespace std;

char Fj[100001];
long long memory[4][21][100001] = {0};
int n;

bool win(const char &p1, const char &p2){
    return ((p1 == 'H' && p2 == 'S') || (p1 == 'S' && p2 == 'P') || (p1 == 'P' && p2 == 'H'));
}

int change(const char &pose){
    if (pose == 'H'){
        return 0;
    }
    else if (pose == 'P'){
        return 1;
    }
    else{
        return 2;
    }
}

int hps(char pose, int k, int i = 0){
    if (memory[change(pose)][k][i]){
        return memory[change(pose)][k][i];
    }
    if (i > n){
        return 0;
    }
    bool flag = win(pose, Fj[i]);
    if (k > 0){
        switch (Fj[i + 1]){
        case 'H':
            if (pose == 'P'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('P', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }

        case 'S':
            if (pose == 'H'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('H', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }

        case 'P':
            if (pose == 'S'){
                memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
                return memory[change(pose)][k][i];
            }
            else{
                memory[change(pose)][k][i] = max(hps('S', k - 1, i + 1) + flag, hps(pose, k, i + 1) + flag);
                return memory[change(pose)][k][i];
            }
        }
    }
    else{
        memory[change(pose)][k][i] = hps(pose, k, i + 1) + flag;
        return memory[change(pose)][k][i];
    }
    return 0;
}

int main(){
    int k;
    cin >> n >> k;
    for (int i = 0; i < n; i++){
        cin >> Fj[i];
    }
    cout << max({hps('S', k), hps('P', k), hps('H', k)});
    return 0;
}