Official Editorial (C++)

Alternate Solution - DP

Explanation

If we define $\texttt{dp}[i][j]$ as the minimum number of skip points needed to get to the $j$th boss on player $i$'s turn (our turn is zero), then our transitions would be:

$\texttt{dp}[0][j + 1] =\min(\texttt{dp}[0][j + 1], \texttt{dp}[1][j] + \texttt{bosses}[j])$

$\texttt{dp}[0][j + 2] =\min(\texttt{dp}[0][j + 2], \texttt{dp}[1][j] + \texttt{bosses}[j] + \texttt{bosses}[j + 1])$

$\texttt{dp}[1][j + 1] =\min(\texttt{dp}[1][j + 1], \texttt{dp}[0][j])$

$\texttt{dp}[1][j + 2] =\min(\texttt{dp}[1][j + 2], \texttt{dp}[0][j])$

This is because from each state, either the previous move, or the previous two moves could have been from the other player.

So, the answer would be $\min(\texttt{dp}[0][N], \texttt{dp}[1][N])$.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int test_case_num;
	cin >> test_case_num;

	for (int t = 0; t < test_case_num; t++) {
		int n;
		cin >> n;

Copy
import java.io.*;
import java.util.Arrays;

public class MortalKombatTower {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCaseNum = Integer.parseInt(br.readLine());

		for (int t = 0; t < testCaseNum; t++) {
			int n = Integer.parseInt(br.readLine());

Copy
for _ in range(int(input())):

	n = int(input())
	bosses = list(map(int, input().split()))

	# dp[i][j] stores the minimum amount of skip points needed for the j-th
	# boss when it is your turn (i = 0) and your friend's turn (i = 1).
	dp = [[float("inf")] * (n + 1) for _ in range(2)]

	dp[0][0] = 0  # Our friend needs to use zero points to fight no bosses.