【问题描述】
某国度的人,喜欢玩这样一个游戏,在一块板上写着一行数,共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;
}
分享到:
相关推荐
本人常年收集的动态规划练习题!!对于熟悉、练习、提高、理解动态规划算法有极大的帮助!!!!!!
动态规划(游艇问题) 数据输入: 第1 行中有1 个正整数n(n≤200),表示有n个游艇出租站。接下来的n-1 行是r(i,j),1≤i≤n。 结果输出: 程序运行结束时,输出从游艇出租站1 到游艇出租站n所需的最少租金。 输入...
算法专项练习--线型动态规划.ppt
(动态规划-分治法-贪心法-回溯法)算法练习题
动态规划习题大全,非常完整,附送答案,动态规划习题大全,非常完整,附送答案,内容不错
贪心算法 ...在每个阶段之后,动态编程基于前一阶段做出的所有决策做出决策,并且可能会重新考虑前一阶段的算法求解路径。 最优子结构 "如果问题的最优解包含子问题的最优解,则该问题表现出最优子结构
动态规划练习必备,数据结构与算法练习必备,oier训练必备,acmer训练必备,互联网企业训练必备,国企笔试必备
这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧。 从斐波那契数列看动态规划 斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的...
国科大计算机算法设计与分析的习题练习题与习题答案,分治算法,贪心算法,动态规划,回溯算法,分治限界算法,
本个文档是针对本人算法课实验讲述的一些课程的个人代码,针对初学者实用性较强,简单易懂,并且算法体系完备,拥有完备的输入和输出。
基于Dijkstra法实现基于栅格地图的移动机器人路径规划算法matlab源码+原理说明文档.zip基于Dijkstra法实现基于栅格地图的移动机器人路径规划算法matlab源码+原理说明文档.zip基于Dijkstra法实现基于栅格地图的移动...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
用c#写的机器调度算法(动态规划),是算法课程的练习题,对理解动态规划的一类问题还是很有帮助的,书上把主要算法已经列出,所以说对代码本身来说是比较简单的!
基于python实现贪心算法、蛮力法、动态规划法解决分数背包问题和0-1背包问题源码(高分课程设计).zip内含详细使用说明文档,个人经导师指导并认可通过的98分大作业设计项目,主要针对计算机相关专业的正在做课程...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...