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普及组复赛 第四题 道路游戏 game.pas

NOIP2009普及组复赛 第四题 道路游戏 game.pas 隐藏>> 4.道路游戏 (game.pas/c/cpp) 【问题描述】 小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,...


NOIP2009普及组第四题道路游戏解题报告

NOIP2009普及组第四题道路游戏解题报告_计算机软件及应用_IT/计算机_专业资料。By FanC . 道路游戏 时间限制: 1000 ms/point 【题目描述】 题目描述】 小新正在玩...


NOIP2009普及组复赛试题

NOIP2009普及组复赛试题_理学_高等教育_教育专区。【NOIP2009】普及组复赛试题复赛...4.道路游戏 . (game.pas/c/cpp) 【问题描述】 小新正在玩一个简单的电脑...


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

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


Noip2009复赛普及组

Noip2009复赛普及组_英语考试_外语学习_教育专区。Noip2009 复赛普及组 1.多项式...4.道路游戏 (game.pas/c/cpp) 【问题描述】 小新正在玩一个简单的电脑游戏...


2009noip复赛试题

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


2000-2011NOIP普及组

2009 2009 2010 2010 2010 2010 2011 2011 2011 2011 细胞分裂 道路游戏 数字...【输出样例】4 【00NOIP 普及组】乘积最大(noip003.pas) 【题目描述】 今年...


NOIP2009解题报告

道路游戏(game.pas) 道路游戏问题转述 有一条环形路,路上有 n 个点,第 i ...NOIP2009普及组解题报告... 9页 1下载券 NOIP2009普及组复赛试题... 3页 免...

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