14450번: Hoof, Paper, Scissors (Gold)

https://www.acmicpc.net/problem/14450


$O(nk)$

dp[i][j]: 앞의 j번의 게임에서 i번 미만 제스쳐를 변화시켰을 때 가능한 최대 승리 횟수
s[i][j]: 1...j번 게임에서 FJ가 i번 제스쳐(발굽, 종이, 가위)를 내놓는 횟수
dp[i][j]=max(k,l)( dp[i-1][k] + s[l][j] - s[l][k] )
이는 dp[i-1][k]-s[l][k]의 누적 최댓값을 구함으로써 빠르게 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, s[3][MXN + 1], dp[22][MXN + 1];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        char c;
        scanf(" %c", &c);
        for (int j = 0; j < 3; j++) s[j][i] += s[j][i - 1] + (j == (c - 'A') / 8);
    }
    for (int i = 1; i <= m + 1; i++) {
        int maxi[3] = { 0,0,0 };
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < 3; k++) {
                maxi[k] = max(maxi[k], dp[i - 1][j] - s[k][j]);
                dp[i][j] = max(dp[i][j], maxi[k] + s[k][j]);
            }
        }
    }
    printf("%d", dp[m + 1][n]);
    return 0;
}