4760: [Usaco2017 Jan]Hoof, Paper, Scissors

4760: [Usaco2017 Jan]Hoof, Paper, Scissors
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 103 Solved: 76 [Submit][Status][Discuss] Description
You have probably heard of the game “Rock, Paper, Scissors”. The cows like to play a similar game th ey call "Hoof, Paper, Scissors"당신은 아마 가위바위보라는 게임을 해 봤을 것입니다. 젖소들도 비슷한 게임을 좋아합니다. "발굽 가위바위보"The rules of "Hoof, Paper, Scissors"are simple입니다.Two cows play against each-other. They both count t o three and then each simultaneously makes a gesture that represents either a hoof, a piece of paper , or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors b eats paper (since scissors can cut paper), and paper beats hoof (since the hoof can get a papercut). For example, if the first cow makes a “hoof” gesture and the second a “paper” gesture, then the sec ond cow wins. Of course, it is also possible to tie, if both cows make the same gesture. 발굽 가위바위보의 규칙은 가위바위보의 규칙과 같다. 발굽 밟기 가위, 가위바위보, 보쌈 발굽 파머, John wants to play against his prize cow, Bessie, at N games of "Hoof, Paper, Scissors"(1≤ N≤100000).Bessie, being an expert at the game, can predict each of FJ’s gestures before he makes i t. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same ge sture multiple times in a row. In fact, she is only willing to switch gestures at most KK times over the entire set of games (0≤K≤20). For example, if K=2, she might play “hoof” for the first few ga mes, then switch to “paper” for a while, then finish the remaining games playing “hoof”. 현재 FJ는 그의 가장 슬기로운 젖소 Bessie와 발굽 가위바위보를 하고 싶어한다(나도 왜 발굽이 있는지 모르겠다). 모두 N라운드(N<=1e5)를 진행했다. B essie는 젖소로서 매우 게으르다. 그녀가 무엇을 내든지 연속적으로 내는 것을 좋아한다. 최대 K회(K<=20)를 변화시킨다. 즉, 그녀가 낸 것에 대해 서열 f(i)로 기록하고sum=i가 얼마나 많은지 만족 f(i)!f(i-1)(i>1), 그녀의 sum은 kGiven the sequence of gestures FJ will be playing, please determine the maximum number of games that Bessiecan win을 넘지 않을 것이다.현재 FJ는 이미 그가 낸 물건을 주었으니, Bessie에게 그녀가 낸 물건이 확실하지 않은 상황에서, 그녀가 최대 몇 번의 Input을 이길 수 있는지 알려줘야 한다
The first line of the input file contains N and K. 입력 데이터 첫 번째 동작 N, K The remaining N lines contains FJ's gestures, each either H, P, or S 다음 N행은 FJ가 낸 것, H는 hoof, P는 페이퍼, S는 Scissors Output
Print the maximum number of games Bessie can win, given that she can only change gestures at most KK times. 출력은 변화가 K번을 넘지 않는 전제에서 최대 몇 번의 Sample Input을 이길 수 있습니까
5 1
P
P
H
P
S Sample Output
4 HINT
Source
Gold
[Submit][Status][Discuss]
usaco 스트로크 시리즈...dp라는 알고리즘이 있어요.

#include
#include
#include
#include
#define max(a,b) ((a) > (b) ? (a) : (b))
using namespace std;

const int maxn = 1E5 + 10;
const int A[3][3] = {{0,1,0},{0,0,1},{1,0,0}};

int n,k,Ans,FJ[maxn],f[maxn][3][21];

map <char,int> M;

inline int Read()
{
    char ch = getchar();
    while (ch < 'A' || 'Z' < ch) ch = getchar();
    return M[ch];
}

int main()
{
    #ifdef DMC
        freopen("DMC.txt","r",stdin);
    #endif

    M['H'] = 0; M['S'] = 1; M['P'] = 2; cin >> n >> k;
    for (int i = 1; i <= n; i++) FJ[i] = Read();
    for (int i = 0; i < 3; i++) f[1][i][0] = A[i][FJ[1]];
    for (int i = 1; i <= n; i++)
        for (int x = 0; x < 3; x++)
            for (int l = 0; l <= k; l++)
            {
                f[i][x][l] = f[i - 1][x][l];
                if (l)
                {
                    for (int y = 0; y < 3; y++)
                        f[i][x][l] = max(f[i][x][l],f[i - 1][y][l - 1]);
                }
                f[i][x][l] += A[x][FJ[i]];
            }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j <= k; j++)
            Ans = max(Ans,f[n][i][j]);
    cout << Ans << endl;
    return 0;
}