# Untitled

unknown

plain_text

2 months ago

3.9 kB

3

Indexable

Never

/*Game with numbers We have a game for you to play with a computer (Com). Your goal is picking numbers from a given array of even length to get maximum scores with the following rules: · The first turn is you, then the turn of computer and so on. · Each turn, you (com) can only pick a number either in the left most or the right most on existing array. · When an element is selected, it will be removed from the array. The game has two levels, the first is very easy - the computer is very stupid, and the second is very hard - the computer is very smart, then the maximum scores you can get in two case may be different. What are the values? For example, if the game have 4 numbers as below 5 8 4 2 In case very easy level, the maximum scores you can get is 13: 1st turn: You pick 5, 2nd turn: Com pick 2, 3rd turn: You pick 8, Last turn: Com pick 4. In case very hard level, the maximum scores you can get is only 10: 1st turn: You pick 2, 2nd turn: Com pick 5, 3rd turn: You pick 8, Last turn: Com pick 4. Note that: if you pick 5 first, then the smart computer will pick 8, so you can get only 9. Therefore the answer for this case is 13 10. Time limit: 10 sec (C/C++), 20 sec (Java). Submit limit: 10 times. [Input] The first line is T (T ≤ 50), the number of test cases. Each test case given on two lines, the first line is the number N (N <= 30), N is even number, the next line is the elements of array, each element is greater than 0 and less than or equals 1000. [Output] Print the answer for each test case on 2 lines, the first line is "Case# x", where x is the test case number. The next line is two numbers, the first is the maximum scores you can get in very easy level, and the next numbers is the maximum scores you can get in very hard level. [Sample] Input: 5 4 5 8 4 2 4 8 5 4 2 ............. Output: Case #1 13 10 Case #2 13 12 Case #3 192 181 Case #4 809 606 Case #5 6175 4557 * */ import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.PrintStream; import java.util.Scanner; public class Gamewithnumbers { static{ try { System.setIn(new FileInputStream("src/inp.txt")); // System.setOut(new PrintStream("src/out.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } } static Scanner scanner=new Scanner(System.in); static int run(int n,int[][] dp,int i,int j){ if(i>j || i>=n || j<0) return 0; if(i==j) return dp[i][i]; if(dp[i][j]==-1){ int a=dp[i][i]+Math.min(run(n,dp,i+2,j),run(n,dp,i+1,j-1)); int b=dp[j][j]+Math.min(run(n,dp,i,j-2),run(n,dp,i+1,j-1)); dp[i][j]=Math.max(a,b); } return dp[i][j]; } static int run2(int n,int[][] dp,int i,int j){ if(i>j || i>=n || j<0) return 0; if(i==j) return dp[i][i]; if(dp[i][j]==-1){ int a=dp[i][i]+Math.max(run2(n,dp,i+2,j),run2(n,dp,i+1,j-1)); int b=dp[j][j]+Math.max(run2(n,dp,i,j-2),run2(n,dp,i+1,j-1)); dp[i][j]=Math.max(a,b); } return dp[i][j]; } static void exec(int ti){ int n=Integer.parseInt(scanner.next()); int[][] dp=new int[n][n],dp2=new int[n][n]; for(int i=0;i<n;++i) for(int j=0;j<n;++j){ dp[i][j]=-1; dp2[i][j]=-1; } for(int i=0;i<n;++i){ dp[i][i]=Integer.parseInt(scanner.next()); dp2[i][i]=dp[i][i]; } int u2=run(n,dp,0,n-1); int u1=run2(n,dp2,0,n-1); System.out.printf("Case #%d\n%d %d\n",ti,u1,u2); } public static void main(String[] args) { int t=Integer.parseInt(scanner.next()); for(int i=1;i<=t;++i) exec(i); scanner.close(); } }