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


NOIP2009普及组解题报告 V1.0

NOIP2009 普及组复赛试题解题报告孙禹达 1、 多项式输出(poly) 问题描述: 给定...4道路游戏(game) 问题描述: 有一条环形路,路上有 n 个点,第 i 个点和...


noip2015普及组题解最终

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


NOIP2009提高组复赛题解

NOIP2009 提高组复赛题解(3) 2010-02-21 20:22 3. 最优贸易 (trade.pas/c/cpp) 【问题描述】 C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个...


NOIP2009解题报告

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


NOIP2008普及组复赛试题与解题报告

NOIP2008普及组复赛试题与解题报告_学科竞赛_初中教育...第 i 行的 4 个整数 Xi, Yi, Pi, Qi, 表示...三、传球游戏(seat.pas/c/cpp) 【问题描述】 上...


NOIP2015普及组复赛解题报告

游戏(mine.cpp/c/pas) 【问题描述】 扫雷游戏是...对于第 3 组至第 4 组数据,1≤n≤3000,1≤m≤...2009NOIP普及组复赛解题... 6页 免费 NOIP2004普及...


noip2015普及组解题报告

扫雷游戏 (mine.cpp/c/pas) 扫雷游戏是一款十分经典的单机小游戏。在 n 行 ...NOIP2010普及组第四题《... 5页 2下载券 NOIP2009普及组第四题道... 4...


NOIP2015普及组解题报告

游戏的目标是在不翻出任何地雷格的条件下,找出所有...对于第 3 组 至第 4 组数据,1 ≤ n ≤ 3000...NOIP2009普及组复赛试题... 3页 免费 2009NOIP...


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

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

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