Mortal Kombat Tower

#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;
 
		vector<int> bosses(n);
		for (int j = 0; j < n; j++) { cin >> bosses[j]; }
 
		/*
		 * dp[i][j] = the min amount of skip points
		 * on turn i (your turn is 0), on the jth boss.
		 * (1e9 to prevent overflow)
		 */
		vector<vector<int>> dp(2, vector<int>(n + 1, 1e9));
 
		/*
		 * base case:
		 * your friend uses zero skip points before fighting any bosses.
		 */
		dp[1][0] = 0;
 
		for (int j = 0; j < n; j++) {
			// the opposite player switches on the previous move.
			dp[0][j + 1] = min(dp[0][j + 1], dp[1][j] + bosses[j]);
			dp[1][j + 1] = min(dp[1][j + 1], dp[0][j]);
 
			// the opposite player switches from the previous two moves.
			if (j + 2 <= n) {
				dp[0][j + 2] = min(dp[0][j + 2], dp[1][j] + bosses[j] + bosses[j + 1]);
				dp[1][j + 2] = min(dp[1][j + 2], dp[0][j]);
			}
		}
		cout << min(dp[0][n], dp[1][n]) << endl;
	}
}

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());
			int[] bosses = Arrays.stream(br.readLine().split(" "))
			                   .mapToInt(Integer::parseInt)
			                   .toArray();
 
			/*
			 * dp[i][j] = the min amount of skip points needed if it is
			 * player i's turn (you are 0 and your friend 1) on the j-th boss.
			 * At the beginning (before fighting any bosses), dp[1][0] = 0.
			 */
			int[][] dp = new int[2][n + 1];
			for (int j = 0; j <= n; j++) {
				dp[0][j] = Integer.MAX_VALUE;
				dp[1][j] = Integer.MAX_VALUE;
			}
			dp[1][0] = 0;
 
			for (int j = 0; j < n; j++) {
				// the opposite player switches on the previous move.
				if (dp[1][j] < Integer.MAX_VALUE) {
					dp[0][j + 1] = Math.min(dp[0][j + 1], dp[1][j] + bosses[j]);
				}
				dp[1][j + 1] = Math.min(dp[1][j + 1], dp[0][j]);
 
				// the opposite player switches from the previous two moves.
				if (j < n - 1) {
					if (dp[1][j] < Integer.MAX_VALUE) {
						dp[0][j + 2] = Math.min(dp[0][j + 2],
						                        dp[1][j] + bosses[j] + bosses[j + 1]);
					}
					dp[1][j + 2] = Math.min(dp[1][j + 2], dp[0][j]);
				}
			}
 
			System.out.println(Math.min(dp[0][n], dp[1][n]));
		}
	}
}

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.
 
	for j in range(len(dp[0]) - 1):
 
		# The opposite player switches on the previous move.
		dp[1][j + 1] = min(dp[1][j + 1], dp[0][j] + bosses[j])
		dp[0][j + 1] = min(dp[0][j + 1], dp[1][j])
 
		# The opposite player switches from the previous two moves.
		if j + 2 < len(dp[0]):
			dp[1][j + 2] = min(dp[1][j + 2], dp[0][j] + bosses[j] + bosses[j + 1])
			dp[0][j + 2] = min(dp[0][j + 2], dp[1][j])
 
	print(min(dp[0][n], dp[1][n]))