Untitled
unknown
plain_text
a year ago
1.4 kB
7
Indexable
Never
package GameWithNumbers; import java.io.FileInputStream; import java.io.PrintStream; import java.util.Scanner; public class Solution { public static void main(String[] args) throws Exception{ System.setIn(new FileInputStream("input.txt")); System.setOut(new PrintStream("output.txt")); Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for (int t = 1; t <= tc; t++) { int n = sc.nextInt(); int[] a = new int[n]; int[][]f = new int[n][n]; int sum = 0; for(int i=0;i<n;i++){ a[i] = sc.nextInt(); sum+=a[i]; } for(int i=0;i<n;i++){ f[i][i] = a[i]; } for(int k=1;k<n;k++){ for(int i=0;i<n-k;i++){ f[i][i+k] = Math.max(a[i]-f[i+1][i+k], a[i+k]-f[i][i+k-1]); } } int score = (sum+f[0][n-1])/2; for(int i = 0;i<n-1;i++){ f[i][i+1] = Math.max(a[i], a[i+1]); } for(int k=2;k<n;k++){ for(int i=0;i<n-k;i++){ f[i][i+k] = Math.max(a[i]+Math.max(f[i+2][i+k],f[i+1][i+k-1]), a[i+k]+Math.max(f[i][i+k-2], f[i+1][i+k-1])); } } int score2 = f[0][n-1]; System.out.println("Case #"+t); System.out.println(score2+" "+score); } } }