Untitled
unknown
plain_text
a month ago
1.9 kB
1
Indexable
Never
import java.util.Scanner; public class Main { public static int maxScores(int[] nums) { int n = nums.length; int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = nums[i]; } for (int length = 2; length <= n; length++) { for (int i = 0; i < n - length + 1; i++) { int j = i + length - 1; dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]); } } return dp[0][n - 1]; } public static void playGame(int T, int[][] testCases) { for (int t = 0; t < T; t++) { int N = testCases[t][0]; int[] elements = new int[N]; elements = testCases[t]; int[] easyLevelElements = new int[N / 2]; int[] hardLevelElements = new int[N / 2]; for (int i = 0; i < N; i++) { if (i % 2 == 0) { easyLevelElements[i / 2] = elements[i]; } else { hardLevelElements[i / 2] = elements[i]; } } int easyLevelScore = maxScores(easyLevelElements); int hardLevelScore = maxScores(hardLevelElements); System.out.println("Case #" + (t + 1)); System.out.println(easyLevelScore + " " + hardLevelScore); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); int[][] testCases = new int[T][]; for (int t = 0; t < T; t++) { int N = scanner.nextInt(); int[] elements = new int[N]; for (int i = 0; i < N; i++) { elements[i] = scanner.nextInt(); } testCases[t] = elements; } playGame(T, testCases); } }