（转）一个游戏得分算法

 

【问题描述】 
某国度的人，喜欢玩这样一个游戏，在一块板上写着一行数，共n个。两个游戏者，轮流从最右或最左取一个数。刚开始，每个游戏者的得分均为20。如果一个游戏者取下一个数，则将该数的值加到该游戏者的得分上，最后谁的得分最高谁就赢了游戏。给出这n个数( 从左往右), 假设游戏者都是非常聪明的，问最后两个人的得分(假设第一个人首先取数)。 
【输入】 
输入格式：第一行为n(2<=n<=100)，第二行为n个数，每个数字之间均用空格隔开。 
【输出】 
输出为两个游戏者的得分。第一个数表示第一个游戏者的得分，第二个数为第二个游戏者的得分，两个数字之间用空格隔开。 

程序运行后结果示例： 
【样例输入】 
6 
4 7 2 9 5 2 
【样例输出】 
38 31

public class ScoreGame { 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
Integer[] examp = new Integer[]{4,7, 2, 9, 5, 2}; 

LinkedList<Integer> queue = new LinkedList<Integer>(); 
queue.addAll(Arrays.asList(examp)); 

int scoreA = scoreFirst(queue)+20; 
int scoreB = calcSum(queue)-scoreA+20; 
System.out.println("A的得分: "+scoreA); 
System.out.println("B的得分: "+scoreB); 
} 

public static int scoreFirst(Deque<Integer> queue){ 
if(queue.size()<2) 
throw new IllegalArgumentException("数组个数不能小于2"); 
if(queue.size()==2){ 
int first = queue.pollFirst(); 
int last = queue.pollLast(); 
return first>=last?first:last; 
}else{ 
int sum = calcSum(queue); 

LinkedList<Integer> pollFirstQueue = new LinkedList<Integer>(queue); 
pollFirstQueue.pollFirst(); 
int result1 = sum - scoreFirst(pollFirstQueue); 

LinkedList<Integer> pollLastQueue = new LinkedList<Integer>(queue); 
pollLastQueue.pollLast(); 
int result2 = sum - scoreFirst(pollLastQueue); 

return result1>result2?result1:result2; 
} 
} 

public static int calcSum(Deque<Integer> queue){ 
int sum = 0; 
for(Integer i:queue){ 
sum+=i; 
} 
return sum; 
} 
} 
运行结果: 
A的得分: 38 
B的得分: 11 

 

 

没有用双端队列的做法:    
public static int scoreFirst2(int[] array, int sIndex, int eIndex) {    
if (eIndex - sIndex < 1)    
throw new IllegalArgumentException("数组个数不能小于2");    
if (eIndex - sIndex == 1) {    
int first = array[sIndex];    
int last = array[eIndex];    
return first >= last ? first : last;    
} else {    
int sum = calcSum(array, sIndex, eIndex);    
int result1 = sum - scoreFirst2(array, sIndex + 1, eIndex);    
int result2 = sum - scoreFirst2(array, sIndex, eIndex - 1);    
return result1 > result2 ? result1 : result2;    
}    
}    
  
public static int calcSum(int[] array, int s, int e) {    
int sum = 0;    
for (int i = s; i <= e; ++i) {    
sum += array[i];    
}    
return sum;    
}