Poj Solution 2738

http://poj.org/problem?id=2738

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
 static final int M = 2,N = 1000+2;
 static int value[] = new int[N];
 static int map[][][] = new int[N][N][M],n;
 public static int Get_Num(StreamTokenizer cin) throws Exception{
    cin.nextToken();
    return (int) cin.nval;
 }

 public static void main(String []args) throws Exception{
        
  int i,k=1;
        
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
    n = Get_Num(cin);
    if(n==0) break;
        
    for(i=1;i<=n;++i) value[i] = Get_Num(cin);
        
System.out.println("In game "+k+", the greedy strategy might lose by as many as "+solve()+" points.");
    ++k;
  }
}

 public static void init_map(){
    int i,j;
    for(i=0;i<=n;++i) for(j=0;j<=n;++j){
        map[i][j][0] = map[i][j][1] = -1;
    }
  }

 public static int max(int a,int b){
    return a>b?a:b;
 }

 public static int get_ans(int left,int right,int p){
  if(map[left][right][p]!=-1)
    return map[left][right][p];
  if(left==right){
    if(p==1) return map[left][right][p] = value[left];
    return map[left][right][p] = 0;
  }
  if(p==1){
return map[left][right][p] = max(get_ans(left,right-1,1-p)+value[right],get_ans(left+1,right,1-p)+value[left]);
  }else{
return map[left][right][p] = (value[right]>value[left]?get_ans(left,right-1,1-p):get_ans(left+1,right,1-p));
 }
}

 public static int solve(){
    int i,k=0;
    init_map();
    for(i=1;i<=n;++i) k+=value[i];
    return get_ans(1,n,1)*2-k;
  }
}