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

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 每日整理
Noip整理 暂无评价 16页 1下载券 Noip整理 暂无评价 5页 2下载券 Noip整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代码汇总整...
Noip整理
或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个...
NOIP算法整理_图文
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
NOIP2014 题解
NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头...(x+p)在展开后必然可以整理成 f(x)+T,其中 T 为关于 p 的一个多项式, ...
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完整考纲_IT/计算机_专业资料。noip需要由本人精心整理,得到的童鞋赚 由本人精心整理,得到的童鞋赚到了哦 标有★的都是 noip 中几乎不可能出现的,没有标的最...
NOIP常用程序段整理
NOIP常用程序段整理 程序程序隐藏>> Noip2009 衢州一中 目录关于时间复杂度 快速排序 归并排序 筛选法求素数 floyed 迪杰斯特拉 prim 拓扑排序 深搜 广搜 最长子序...
2016.10.1 学习整理
2016.10.1 学习整理_教育学_高等教育_教育专区。2016.10.1 期清北学堂整理 ...(NOIP 不过多涉及这方面的知识) 并查集(这才是 NOIP 真正用得到的) 并查集是...
NOIP复习资料
虽然资料是用 Pascal 语言写的,但是没关系——我了解一些 P 的代码,整理笔记...(i=0;i<n;i++) // 存储状态 // 获取状态 24 NOIP 复习资料(C++版) ...
更多相关标签:
noip2016 | noip动态域名注册 | noip吧 | noip2016提高组复赛 | noip2016普及组复赛 | noip官网 | noip2015提高组复赛 | noip2015普及组复赛 |