# 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;

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;
}
}

```
This entry was posted in poj. Bookmark the permalink.