简答题 偏难
#23649

道路游戏 【问题描述】 小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器…

道路游戏

【问题描述】

小新正在玩一个简单的电脑游戏。

游戏中有一条环形马路,马路上有 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. 购买机器人和设定机器人的行走次数是瞬间完成的,不需要花费时间。

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 个单位时间内,扣除购买机器人

花费的金币之后,小新最多能收集到多少金币。

【输入输出样例】

【数据范围】

对于 40%的数据,2≤ n≤ 40,1≤ m ≤ 40。

对于 90%的数据,2≤ n≤ 200,1≤ m ≤ 200。

对于 100%的数据,2≤ n≤ 1000,1≤ m≤ 1000,1≤p≤ m。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>#include &lt;bits/stdc++.h&gt; </p><p>using namespace std;</p><p>int n,m,p,b[1001],a[1001][1001],f[1001];</p><p>int main(){</p><p>    scanf("%d%d%d",&amp;n,&amp;m,&amp;p);//n表示工厂和马路的数量,m表示游戏时间,p表示机器人能穿过的工厂数量 </p><p>    memset(f,-1000000,sizeof(f)); </p><p>    f[0]=0;</p><p>    for(int i=1; i&lt;=n; i++)</p><p>        for(int j=1; j&lt;=m; j++) </p><p>            scanf("%d",&amp;a[i][j]);//a[i,j]表示在第i段马路上 在第j秒时的金币数量 </p><p>    for(int i=1; i&lt;=n; i++) </p><p>      scanf("%d",&amp;b[i]);//b[i]表示在第i个工厂购买机器人的价格 </p><p>    for(int i=1; i&lt;=m; i++)</p><p>        for(int j=1; j&lt;=n; j++){//j表示机器人的编号 </p><p>            int pre=j-1;// 机器人上一次在第pre个工厂 </p><p>            if(pre==0) pre=n;//如果t等于0(被1减了),那么就是从第n个过来的 </p><p>            int sum=a[pre][i];//sum表示在第pre段马路上第i秒时的金币数量 </p><p>            for(int k=1; k&lt;=p; k++){//k表示在第i秒时第j个机器人走了k步 </p><p>                if(i-k&lt;0) break;//时间不会是负的 </p><p>                f[i]=max(f[i],f[i-k]+sum-b[pre]);// f[i]表示第i秒时能获得的最大钱数 </p><p>                pre--;</p><p>                if(pre==0) pre=n;//跑道环形 </p><p>                sum+=a[pre][i-k];</p><p>            }</p><p>        }</p><p>    printf("%d",f[m]);</p><p>    return 0;</p><p>}</p>
这道题暂未补解析。