tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOIP2009普及组复赛 第四题 道路游戏 game.pas


4.道路游戏 (game.pas/c/cpp) 【问题描述】 小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段 马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n 个机器人工厂编号为 1~n,因为马路是环形的,所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在 一起的。小新将连接机器人工厂的

这 n 段马路也编号为 1~n,并规定第 i 段马路连接第 i 个 机器人工厂和第 i+1 个机器人工厂(1 ≤ i ≤ n-1),第 n 段马路连接第 n 个机器人工厂和 第1 个机器人工厂。 游戏过程中,每个单位时间内,每段马路上都会出现一些金币,金币的数量会随着时间 发生变化,即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人 的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买,机器 人一旦被购买,便会沿着环形马路按顺时针方向一直行走,在每个单位时间内行走一次,即 从当前所在的机器人工厂到达相邻的下一个机器人工厂,并将经过的马路上的所有金币收集 给小新,例如,小新在 i(1 ≤ i ≤ n)号机器人工厂购买了一个机器人,这个机器人会从 i 号 机器人工厂开始,顺时针在马路上行走,第一次行走会经过 i 号马路,到达 i+1 号机器人工 厂(如果 i=n,机器人会到达第 1 个机器人工厂),并将 i 号马路上的所有金币收集给小新。 游戏中,环形马路上不能同时存在 2 个或者 2 个以上的机器人,并且每个机器人最多能 够在环形马路上行走 p 次。小新购买机器人的同时,需要给这个机器人设定行走次数,行走 次数可以为 1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失,小 新必须立刻在任意一个机器人工厂中购买一个新的机器人,并给新的机器人设定新的行走次 数。 以下是游戏的一些补充说明: 1. 游戏从小新第一次购买机器人开始计时。 2. 购买机器人和设定机器人的行走次数是瞬间完成的,不需要花费时间。 全国信息学奥林匹克联赛(NOIP2009)复赛普及组 第 6 页共 6 页 3. 购买机器人和机器人行走是两个独立的过程,机器人行走时不能购买机器人,购买 完机器人并且设定机器人行走次数之后机器人才能行走。 4. 在同一个机器人工厂购买机器人的花费是相同的,但是在不同机器人工厂购买机器

人的花费不一定相同。 5. 购买机器人花费的金币,在游戏结束时再从小新收集的金币中扣除,所以在游戏过 程中小新不用担心因金币不足,无法购买机器人而导致游戏无法进行。也因为如此, 游戏结束后,收集的金币数量可能为负。 现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人 需要的花费,请你告诉小新,经过 m 个单位时间后,扣除购买机器人的花费,小新最多能 收集到多少金币。 【输入】 输入文件名为 game.in。 第一行 3 个正整数,n,m,p,意义如题目所述。 接下来的 n 行,每行有 m 个正整数,每两个整数之间用一个空格隔开,其中第 i 行描 述了 i 号马路上每个单位时间内出现的金币数量(1 ≤ 金币数量≤ 100),即第 i 行的第 j (1 ≤ j ≤m)个数表示第 j 个单位时间内 i 号马路上出现的金币数量。 最后一行,有 n 个整数,每两个整数之间用一个空格隔开,其中第 i 个数表示在 i 号机 器人工厂购买机器人需要花费的金币数量(1 ≤ 金币数量≤ 100)。 【输出】 输出文件 game.out 共一行,包含 1 个整数,表示在 m 个单位时间内,扣除购买机器人 花费的金币之后,小新最多能收集到多少金币。 【输入输出样例】 game.in game.out 2 3 2 1 2 3 2 3 4 1 2 5 【数据范围】 对于 40%的数据,2 ≤ n ≤ 40,1 ≤m≤ 40。 对于 90%的数据,2 ≤ n ≤ 200,1 ≤m≤ 200。 对于 100%的数据,2 ≤ n ≤ 1000,1 ≤m≤ 1000,1 ≤ p ≤m

var f:array[0..1000] of longint; map:array[1..1000,1..1000] of integer;

dz:array[1..1000,1..1000] of longint; mac:array[1..1000] of integer; n,m,p:integer; i,j,k:integer; function getmax(ge:integer):longint; var i:integer; begin getmax:=0; for i:=1 to n do if getmax<dz[i,ge] then getmax:=dz[i,ge]; end; procedure getdz(x,y,z:integer); var p1:integer;te:longint;gx,gy:integer; begin p1:=1; te:=f[y-1]+map[x,y]-mac[x];if te>dz[x,y] then dz[x,y]:=te; gx:=x+1;gy:=y+1; repeat while (gx<=n)and(p1<z) do begin te:=te+map[gx,gy]; if te>dz[gx,gy] then dz[gx,gy]:=te; inc(gx);inc(gy);inc(p1); end; if p1>=z then exit; gx:=1; until 1=0; end; begin fillchar(f,sizeof(f),0); readln(n,m,p); for i:=1 to n do

for j:=1 to m do dz[i,j]:=-2048; for i:=1 to n do begin for j:=1 to m do read(map[i,j]); readln; end; for i:=1 to n do read(mac); f[0]:=0; for j:=1 to m-p+1 do begin for i:=1 to n do getdz(i,j,p); f[j]:=getmax(j); end; for j:=m-p+2 to m do begin for i:=1 to n do getdz(i,j,m-j+1); f[j]:=getmax(j); end; write(f[m]); end.

上面是题目,下面是我做的过程、 写的如何?高手来指点一 下、因为就剩下最后 10%那两个测试数据点没有过,其它的 90%都在 0.2s 内过了、


推荐相关:

全国信息学奥林匹克联赛(NOIP2009)复赛普及组

全国信息学奥林匹克联赛(NOIP2009)复赛普及组 第 1 页共 6 页 全国信息学奥...4.道路游戏 (game.pas/c/cpp) 【问题描述】 小新正在玩一个简单的电脑游戏...


NOIP2010普及组复赛试题

NOIP2010普及组复赛试题_初三数学_数学_初中教育_...4.三国游戏 (sanguo.pas/c/cpp) 【问题描述】 ...文档贡献者 RoyTop_Gu 贡献于2010-12-09 ...


NOIP2015普及组复赛试题

NOIP2015普及组复赛试题_学科竞赛_初中教育_教育专区。CCF 全国信息学奥林匹克...CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 2. 扫雷游戏 (mine.cpp/c/pas)...


noip2008普及组复赛试题(附题解)

传球游戏 ball ball ball.in ball.out 1秒 10 10...(NOIP2008)复赛 普及组 4.立体图(drawing.pas/c/...NOIP2009普及组复赛试题... 3页 免费 ©...


2009noip复赛试题

全国信息学奥林匹克联赛(NOIP2009)复赛普及组 第 3 页共 6 页 2.分数线...4.道路游戏 (game.pas/c/cpp) 问题描述】 【问题描述】 小新正在玩一个简单...


NOIP2015普及组复赛试题解题报告word版第一二题满分程序

NOIP2015普及组复赛试题解题报告word版第一二题满分程序_学科竞赛_初中教育_教育...扫雷游戏(mine.cpp/c/pas) 【问题描述】 扫雷游戏是一款十分经典的单机小游戏...


NOIP2010普及组第四题《三国游戏》解题报告

NOIP2010 普及组第四题 三国游戏 解题报告 (sanguo.pas/c/cpp) 【问题描述】 小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。 在游戏中, 小涵和...


NOIP2003普及组复赛试题

NOIP2003普及组复赛试题_初一数学_数学_初中教育_教育专区。NOIP2003普及组NOIP...1 题二,数字游戏(Game.pas) 【问题描述】丁丁最近沉迷于一个数字游戏之中....


NOIP2015普及组复赛解题报告

【思路】 模拟 【时空复杂度】 O(k),O(1) 2、扫雷游戏(mine.cpp/c/pas...2009NOIP普及组复赛解题... 6页 免费 NOIP2004普及组复赛解题... 8页 免费...


noip2015普及组题解最终

noip2015普及组题解最终_学科竞赛_小学教育_教育专区...每天收到两枚金币;第四、五、六天,每 天收到三...2.扫雷游戏(mine.cpp/c/pas) 【问题描述】 扫雷...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com