Question 2 / 2 (Amazon Campus(9): MM-Chess)
There is an interesting game called MM-Chess. The size of the board is 1*N, every grid has a score (non-negative). The first grid is the start and the Nth grid is the end. The game requires players to control the chess starting from the starting point to
the end.
There're four types of cards in the game and the total number is M. Each type of card are labeled one integer number in [1,4]. After using a card with number x on it, the chess will move x steps forward. Each time, player will choose one unused card to move
the chess forward, and each card can only be used once. In the game, the chess gains the score at the starting point automatically. When the chess arrives at a new grid, it also gets the score on that point. The goal of the game is to get the most score.
Input:
The first line contains two integers N (the size of board) and M (the number of the cards).
The second line contains N integers, meaning the scores on the the board (the i-th integer corresponds to the score on the i-th grid).
The third line contains M integers, meaning the numbers on the M cards.
The sum of the number of M cards equals to N-1.
You can assume that 1 <= N <= 350, 1 <= M <= 120, and that the number of cards are less than 40 for each kind.
Output:
One integer. The most score that player can get.
Sample Input 1
4 2
1 2 1 2
1 2
Sample Output 1
5
Given two cards with number 1 and number 2 each, we have two choices: path one is 1 -> 2 -> 2, path two is 1 -> 1 -> 2. The maximum score is 5, which is the output.
Sample Input 2
5 3
1 2 1 2 1
1 2 1
Sample Output 2
6
Given three cards (one can move 2 steps, two can move 1 steps), we have three choices: path one is 1 -> 2 -> 1 -> 1, path two is 1 -> 2 -> 2 -> 1, path three is 1 -> 1 -> 2 -> 1. The maximum score is 6, which is the output.
static int MMchess(int[] Nscores, int[] Mnumbers) {
// Nscores : the scores on the the board (the i-th integer corresponds to the score on the i-th grid)
// Mnumbers : the numbers on the M cards
// return value : the most score that player can get
if(Mnumbers.length == 0) return Nscores[0];
int max = 0;
for(int i=0; i<Mnumbers.length; i++) {
int score = Nscores[0];
int []tempNscores = new int[Nscores.length-Mnumbers[i]];
for(int j=Mnumbers[i],k=0; j<Nscores.length; j++) {
tempNscores[k] = Nscores[j];
k++;
}
int []tempMnumbers = new int[Mnumbers.length-1];
for(int j=0,k=0; j<Mnumbers.length; j++) {
if(j==i) continue;
tempMnumbers[k] = Mnumbers[j];
k++;
}
score += MMchess(tempNscores, tempMnumbers);
if(max < score) max = score;
}
return max;
}
上述采用递归,大数据量时TLE。可采用动态规划:
dp[type1][type2][type3][type4]=
max{
dp[type1-1][type2][type3][type4]+sorce,
dp[type1][type2-1][type3][type4]+score,
dp[type1][type2][type3-1][type4]+score,
dp[type1][type2][type3][type4-1]+score
}
分享到:
相关推荐
(*)为e-chess sudo docker pull coderon98/e-chess:beta : sudo docker pull coderon98/e-chess:beta (**)构建docker容器并运行它: sudo docker run -it --name e-chess -e DISPLAY=$DISPLAY -v /tmp/.X11-...
Chess Clock App Description: A game-clock app for the Android mobile devices. Useful in blitz chess games and bug-house. License: Unless specified otherwise, this application is under the MIT license....
资源分类:Python库 所属语言:Python 资源全名:django-chess-0.2.0.tar.bz2 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
国际象棋-Python-AI描述使用进行AI扭曲的经典国际象棋怎么玩怎么玩从安装Python 从安装PyGame 1.9.X 克隆此存储库: ... 从python3 Chess/main.py的根目录运行python3 Chess/main.py 玩得开心!预览
伊万娜·象棋 象棋游戏。 如何建造 ./gradlew assemble 测试方法 ./gradlew check 如何运行API ...docker run -p 80:80 -e ' API_BASE_URL=http://localhost:4200 ' gleroy/ivana-chess-webapp API文档
语言:English (United States) 用于chess.com的开源Chrome... 源代码: https://github.com/chess-digital-rain/chess-digital-rain 请求或问题: https://github.com/chess-digital-rain/chess-digital-rain/issues
ISO 13818 -1 2 3 视频、系统、编码、音频规范
名称:Chess.com Analysis at Lichess -------------------- 版本:4.0.3 作者:Robert Anderson 分类:休闲娱乐 -------------------- 概述:从 chess.com 或 chessgames.com 在 lichess.org 分析中打开游戏的 PGN...
IOS应用源码——vonProteus-iPhone-OpenGL-Chess-8636ccc.rar
资源分类:Python库 所属语言:Python 资源全名:chess-cheat-0.0.14.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
互联网象棋杀手为自动使用的国际象棋... 高于2,3,3.1 DEMO,3.1 FULL CRACKED的版本仅是exe二进制文件。 您可以观看视频: 您可以在论坛上交谈: http://www.chessgod101.com/t2647-internet-chess-killer http://w
资源分类:Python库 所属语言:Python 资源全名:chess-game-0.2.4.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
步骤2:安装软件包。 以下是可以单独安装的核心功能。 chess==1.3.0 pytorch-lightning==0.9.0 torch==1.7.1 transformers==4.2.2 prettytable==0.7.2 或者只是做: pip install -r requirements.txt 最后 cd src/...
象棋 :chess_pawn: 健身房的简单国际象棋环境。 它计算所有可用的举动,包括小举,典当促销和3倍重复抽奖。 8 ♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜ 7 :chess_pawn: :chess_pawn: :chess_pawn: :chess_pawn: ...
资源来自pypi官网。 资源全名:chess-tuning-tools-0.7.0b2.tar.gz
python库。 资源全名:python-chess-0.8.0.tar.gz
它是 Stockfish Chess 引擎的 Web 图形用户界面 (GUI)。 它是一个功能齐全的基于网络的国际象棋应用程序,可让您与 Stockfish 国际象棋引擎对战。 使命 我们在这个项目中的任务是开发一个由 Stockfish 国际象棋引擎...
chess:js-chess游戏
c-chess-cli c-chess-cli是用于用C编写的UCI国际象棋引擎的命令行界面。没有,它仅使用C标准库和POSIX。它最初是在Linux上开发的,应该可以在所有POSIX操作系统上使用,包括MacOS和Android。不支持Windows。如何编译...
3D-04-Low-Poly-Chess-Set-Original.zip,低保利国际象棋(CS_CBC)http://gdev.tv/cbcgithub,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用...