当前位置:首页 >> 学科竞赛 >>

Noip整理


[NOIP2010]乌龟棋 From
NOIP2010提高组复赛第二题

描述 Description 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行 N 个格子,每个格子上一个分数(非负整数) 。棋盘第1 格 是唯一的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走 到终点。1 2 3 4 5 …… N 乌龟棋中 M 张爬行卡片, 分成4 种不同的类型 (M 张卡片中不一定包含所有4 种 类型的卡片,见样例) ,每种类型的卡片上分别标有1、2、3、4 四个数字之一, 表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需 要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片, 控制乌龟棋子前进 相应的格子数,每张卡片只能使用一次。 游戏中, 乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格 子, 就得到该格子相应的分数。 玩家最终游戏得分就是乌龟棋子从起点到终点过 程中到过的所有格子的分数总和。 很明显, 用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到 一种卡片使用顺序使得最终游戏得分最多。 现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多 能得到多少分吗? 输入格式 InputFormat 输入文件的每行中两个数之间用一个空格隔开。 第1 行2 个正整数 N 和 M,分别表示棋盘格子数和爬行卡片数。

第2 行 N 个非负整数,a1,a2,……,aN,其中 ai 表示棋盘第 i 个格子上的分 数。 第3 行 M 个整数,b1,b2, ……, bM,表示 M 张爬行卡片上的数字。 输入数据保证到达终点时刚好用光 M 张爬行卡片 输出格式 OutputFormat 输出只有1 行,1 个整数,表示小明最多能得到的分数。 样例输入 SampleInput 输入样例1 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 输入样例2 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1 样例输出 SampleOutput 输出样例1 73 输出样例2 455 【数据范围】 对于30%的数据有1 ≤ N≤ 30,1 ≤M≤ 12。 对于50%的数据有1 ≤ N≤ 120,1 ≤M≤ 50,且4 种爬行卡片,每种卡片的张 数不会超 过20。

对于100%的数据有1 ≤ N≤ 350,1 ≤M≤ 120,且4 种爬行卡片,每种卡片的 张数不会 超过40;0 ≤ ai ≤ 100,1 ≤ i ≤ N;1 ≤ bi ≤ 4,1 ≤ i ≤M。

var n,m:longint; x,y,z,w:longint; f:array[-10..40,-10..40,-10..40,-10..40] of longint; a,b:array[0..1000] of longint; procedure init; var i,x,temp,num:longint; begin readln(n,m); for i:=1 to n do read(a[i]); for i:=1 to m do begin read(x); b[x]:=b[x]+1; end; end; function max(a,b:longint):longint; begin

if a>b then exit(a) else exit(b); end; procedure solve; begin f[0,0,0,0]:=a[1]; for x:=0 to b[1] do for y:=0 to b[2] do for z:=0 to b[3] do for w:=0 to b[4] do begin

f[x,y,z,w]:=max(f[x-1,y,z,w],max(f[x,y-1,z,w],max(f[x,y,z-1,w],f[x,y ,z,w-1])))+a[x+2*y+3*z+4*w+1]; end; writeln(f[b[1],b[2],b[3],b[4]]); end; begin init; solve; end.


相关文章:
Noip整理
Noip整理_学科竞赛_高中教育_教育专区。团伙 背景 Background From BearHsu 经典题目描述 Description 1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他 ...
Noip整理
或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个...
noip 每日整理
Noip整理 暂无评价 16页 1下载券 Noip整理 暂无评价 5页 2下载券 Noip整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代码汇总整...
NOIp每日整理
["扫地"杯 III day1]诡异的数学题 From liouzhou_101 背景 Background “扫地”杯 III NOIP2012模拟赛 day1 第一题描述 Description liouzhou_101从 NOI 归来...
NOIP算法整理_图文
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(NOIP)必看经典书目汇总! 小编整理汇总了一下大神们极力推荐的复习资料! (欢迎大家查漏...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(NOIP)必看经典书目汇总! 小编整理汇总了一下大神们极力推荐的复习资料! (欢迎大家查漏...
NOIP复习资料(C++版)_图文
前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言 有一天,我整理NOIP 的笔记,并收集了一些经典算法。...
Noip图论整理
图论程序整理 Edmonds-Karp var ans,i,j,k,s,t,tot,m,n,a,b,c:longint; u,v,w,next,other:array[0..200] of longint; point,d,q,pre:array[0...
冲刺NOIP之整理
NOIP范围内的DP算法 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP整理 冲刺NOIP2012知识点整理、冲...
更多相关标签: