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

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每日整理
["扫地"杯 III day1]诡异的数学题 From liouzhou_101 背景 Background “扫地”杯 III NOIP2012模拟赛 day1 第一题描述 Description liouzhou_101从 NOI 归来...
noip文件操作(亲自整理)(全)
Noip 专用文件输入输出(本人亲自整理)例一 #include "stdio.h" int main() {FILE *fp,*f; inta,b,c; fp=fopen("apple1.txt","r"); f=fopen("apple...
noip 每日整理
Noip整理 暂无评价 16页 1下载券 Noip整理 暂无评价 5页 2下载券 Noip整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代码汇总整...
NOIP算法整理_图文
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
NOIP常用程序段整理
NOIP常用程序段整理 程序程序隐藏>> Noip2009 衢州一中 目录关于时间复杂度 快速排序 归并排序 筛选法求素数 floyed 迪杰斯特拉 prim 拓扑排序 深搜 广搜 最长子序...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(NOIP)必看经典书目汇总! 小编整理汇总了一下大神们极力推荐的复习资料! (欢迎大家查漏...
冲刺NOIP之整理
NOIP范围内的DP算法 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP整理 冲刺NOIP2012知识点整理、冲...
NOIP2014 题解
NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头...(x+p)在展开后必然可以整理成 f(x)+T,其中 T 为关于 p 的一个多项式, ...
noip的总结
noip 总结 1 算法总结动规难点:模型的建立和理解。 要求:对于每道题,都能在很短的时间里把思路完整地整理一遍,可以快速而无误的写 出程序。 (一) 两种动机 ...
更多相关标签:
noip动态域名注册 | noip吧 | noip2016 | noip2016普及组复赛 | noip2015 | noip一等奖有什么用 | noip题库 | noip 竞赛 |