做网站优化需要多少钱,wordpress好看博客主题,最大的源码分享平台,职业技能培训平台小明过生日的时候#xff0c;爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘只有一行#xff0c;该行有 N 个格子#xff0c;每个格子上一个分数#xff08;非负整数#xff09;。
棋盘第 1 格是唯一的起点#xff0c;第 N 格是终点#xff0c;游戏要求玩家控制一个乌龟…小明过生日的时候爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘只有一行该行有 N 个格子每个格子上一个分数非负整数。
棋盘第 1 格是唯一的起点第 N 格是终点游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中共有 M 张爬行卡片分成 4 种不同的类型M 张卡片中不一定包含所有 4 种类型的卡片每种类型的卡片上分别标有1、2、3、4 四个数字之一表示使用这种卡片后乌龟棋子将向前爬行相应的格子数。
游戏中玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片控制乌龟棋子前进相应的格子数每张卡片只能使用一次。
游戏中乌龟棋子自动获得起点格子的分数并且在后续的爬行中每到达一个格子就得到该格子相应的分数。
玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显用不同的爬行卡片使用顺序会使得最终游戏的得分不同小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在告诉你棋盘上每个格子的分数和所有的爬行卡片你能告诉小明他最多能得到多少分吗
输入格式 输入文件的每行中两个数之间用一个空格隔开。
第 1 行 2 个正整数 N 和 M分别表示棋盘格子数和爬行卡片数。
第 2 行 N 个非负整数a1,a2,……,aN其中 ai 表示棋盘第 i 个格子上的分数。
第 3 行 M 个整数b1,b2,……,bM表示 M 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 M 张爬行卡片。
输出格式 输出只有 1 行包含 1 个整数表示小明最多能得到的分数。
数据范围 1≤N≤350, 1≤M≤120, 0≤ai≤100, 1≤bi≤4, 每种爬行卡片的张数不会超过40。
输入样例 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 输出样例 73
代码如下
#include iostream
using namespace std;
const int N 42;
int f[N][N][N][N];
int b[355];
int score[355];
int main()
{int n,m;cinnm;for (int i 0;in;i) cinscore[i];for (int i 0;im;i){int x;cinx;b[x];}f[0][0][0][0] score[0];for (int A 0;Ab[1];A)for (int B 0;Bb[2];B)for (int C 0;Cb[3];C)for (int D 0;Db[4];D){int s score[A*1B*2C*3D*4];int t f[A][B][C][D];if (A) t max(t,f[A-1][B][C][D]s);if (B) t max(t,f[A][B-1][C][D]s);if (C) t max(t,f[A][B][C-1][D]s);if (D) t max(t,f[A][B][C][D-1]s);}coutf[b[1]][b[2]][b[3]][b[4]]endl;
}
