Hoof, Paper, Scissors

// CodeSnip{CPP Short Template}
 
const int MX = 1e5 + 5;
 
int dp[MX][25][3];  // dp[i][j][k] es la mayor cantidad de juegos que gana en
                    // el juego i con j cambios y el ítem actual k
int moves[MX];      // 0 == H 1 == P 2 == S
 
int main() {
	setIO("hps");
 
	int N, K;
 
	cin >> N >> K;
 
	for (int i = 0; i < N; i++) {
		char a;
		cin >> a;
		if (a == 'H') moves[i] = 0;
		if (a == 'P') moves[i] = 1;
		if (a == 'S') moves[i] = 2;
	}
 
	// o cambia a h o p o s o se queda
 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= K; j++) {
			for (int k = 0; k < 3; k++) {
 
				// Si la estrategia actual coincide con el movimiento del oponente, incrementar el conteo de victorias
				if (k == moves[i]) dp[i][j][k]++;
				dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0],
				                          dp[i][j][k]);  // cambiar a pezuña
				dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1],
				                          dp[i][j][k]);  // cambiar a papel
				dp[i + 1][j + 1][2] = max(dp[i + 1][j + 1][2],
				                          dp[i][j][k]);  // cambiar a tijera
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);  // quedarse
			}
		}
	}
 
	int ret = 0;
 
	for (int i = 0; i < 3; i++) { ret = max(ret, dp[N - 1][K][i]); }
 
	cout << ret << endl;
}

import java.io.*;
import java.util.*;
 
public class HoofPaperScissors {
	static int[] moves;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("hps.in"));
		StringTokenizer inputLine = new StringTokenizer(br.readLine());
		int numGames = Integer.parseInt(inputLine.nextToken());
		int maximumSwitches = Integer.parseInt(inputLine.nextToken());
 
		// dp[juego][cambios][tipo] = cantidad máxima de victorias
		// en ese juego con a lo sumo esa cantidad
		// de cambios y con ese tipo activo
		moves = new int[numGames + 1];
		for (int x = 1; x <= numGames; x++) {
			char c = br.readLine().charAt(0);
			// poner H como 0, P como 1, S como 2
			if (c == 'H') {
				moves[x] = 0;
			} else if (c == 'P') {
				moves[x] = 1;
			} else {
				moves[x] = 2;
			}
		}
 
		int[][][] dp = new int[numGames + 1][maximumSwitches + 2][3];
		int maximum = 0;
 
		/*
		 * c = número de juego actual
		 * n = cantidad de cambios
		 */
		for (int c = 1; c <= numGames; c++) {
			// para cada cantidad de cambios
			for (int n = 1; n < maximumSwitches + 2; n++) {
				// intentar cambiar a las tres posibilidades
				int add1 = 0;
				if (moves[c] == 0) { add1 = 1; }
				// tomar el máximo del juego anterior + add (ganar o perder)
				// y cambiar desde las otras dos opciones
				dp[c][n][0] = Math.max(
				    dp[c - 1][n][0] + add1,
				    Math.max(dp[c - 1][n - 1][1] + add1, dp[c - 1][n - 1][2] + add1));
 
				int add2 = 0;
				if (moves[c] == 1) { add2 = 1; }
				dp[c][n][1] = Math.max(
				    dp[c - 1][n][1] + add2,
				    Math.max(dp[c - 1][n - 1][0] + add2, dp[c - 1][n - 1][2] + add2));
 
				int add3 = 0;
				if (moves[c] == 2) { add3 = 1; }
				dp[c][n][2] = Math.max(
				    dp[c - 1][n][2] + add3,
				    Math.max(dp[c - 1][n - 1][0] + add3, dp[c - 1][n - 1][1] + add3));
 
				if (c == numGames) {  // comprobar el máximo si es la última fila
					maximum = Math.max(maximum, Math.max(dp[numGames][n][0],
					                                     Math.max(dp[numGames][n][1],
					                                              dp[numGames][n][2])));
				}
			}
		}
 
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("hps.out")));
		pw.println(maximum);
		pw.close();
	}
}

with open("hps.in") as read:
	n, k = map(int, read.readline().strip().split())
	moves = [0] * n
	for i in range(n):
		a = read.readline().strip()
		if a == "H":
			moves[i] = 0
		elif a == "P":
			moves[i] = 1
		else:
			moves[i] = 2
 
"""
dp[i][j][k] es la cantidad máxima de juegos que gana en
el i-ésimo juego después de j cambios con el ítem actual k
H = 0, P = 1, S = 2
"""
dp = [[[0] * 3 for _ in range(k + 1)] for _ in range(n + 1)]
 
# o cambia a pezuña o papel o tijera o se queda
for i in range(n):
	for j in range(k + 1):
		for l in range(3):
 
			# Si la estrategia actual coincide con el movimiento del oponente, incrementar el conteo de victorias
			if l == moves[i]:
				dp[i][j][l] += 1
 
			if j != k:
				# cambiar a pezuña
				dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0], dp[i][j][l])
 
				# cambiar a papel
				dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1], dp[i][j][l])
 
				# cambiar a tijera
				dp[i + 1][j + 1][2] = max(dp[i + 1][j + 1][2], dp[i][j][l])
 
			# quedarse
			dp[i + 1][j][l] = max(dp[i + 1][j][l], dp[i][j][l])
 
res = 0
for i in range(3):
	res = max(res, dp[n - 1][k][i])
 
print(res, file=open("hps.out", "w"))