P1070 道路游戏

题目描述

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

游戏中有一条环形马路,马路上有 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 个单位时间后,扣除购买机器人的花费,小新最多能收集到多少金币。

输入输出格式

输入格式:

第一行 3 个正整数,n,m,p,意义如题目所述。

接下来的 n 行,每行有 m 个正整数,每两个整数之间用一个空格隔开,其中第 i 行描

述了 i 号马路上每个单位时间内出现的金币数量(1≤金币数量≤100),即第 i 行的第 j(1≤j≤m)个数表示第 j 个单位时间内 i 号马路上出现的金币数量。

最后一行,有 n 个整数,每两个整数之间用一个空格隔开,其中第 i 个数表示在 i 号机器人工厂购买机器人需要花费的金币数量(1≤金币数量≤100)。

输出格式:

共一行,包含 1 个整数,表示在 m 个单位时间内,扣除购买机器人

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

输入输出样例

输入样例#1:

2 3 2 
1 2 3 
2 3 4 
1 2

输出样例#1:

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。

NOIP 2009 普及组 第四题

一开始想到一个思路.

用dp[i][j][l]表示第i个时间点,在第j个地方,走了l步的最大收益,后来一看数据范围发现肯定过不了。

我们用dp[i]表示在第i个时间点的最小花费,因为最后没有询问j和l,而且j和l我们可以通过暴力枚举出来,所以可以优化掉

对于每个时间的地点,因为购买机器人之后机器人最多可以走p步,所以我们可以从j向前枚举p个节点,

因为这道题有点类似于无向图,所以这样枚举是可行的

每次计算出在当前时间点的最小花费,

因为每走一步需要花费一个时间点,所以now每次加上i-k的时间的收益就好,

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=1001;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
11     while(c>='0'&&c<='9')
12     {x=x*10+c-48;c=getchar();}
13     flag==1?n=-x:n=x;
14 }
15 int dp[MAXN];
16 // 第i个时间点,在第j个地方
17 int n;// 节点。
18 int m;//单位时间
19 int p;//行走次数 
20 int mon[MAXN][MAXN];
21 int spend[MAXN];
22 int pre(int p)
23 {
24     if(p==1)
25         return n;
26     else return p-1;
27 }
28 int main()
29 {
30     read(n);read(m);read(p);
31     for(int i=1;i<=n;i++)
32         for(int j=1;j<=m;j++)
33             read(mon[i][j]);
34     for(int i=1;i<=n;i++)
35         read(spend[i]);
36     for(int i=1;i<=m;i++)
37     {
38         for(int j=1;j<=n;j++)
39         {
40             int r=pre(j),now=0;
41             now=mon[r][i];// 初始化
42             for(int k=1;k<=p;k++)
43             {
44                 if(i-k<0)break;
45                 dp[i]=max(dp[i],dp[i-k]-spend[r]+now);
46                 r=pre(r);
47                 now+=mon[r][i-k];
48             } 
49         }
50     }
51     printf("%d",dp[m]);
52     return 0;
53 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闰土大叔

太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考察...

1173
来自专栏Crossin的编程教室

你“听”过这些经典排序算法吗?

算法是编程知识体系中的重要部分。当你已经掌握了一些编程基础之后,必然需要了解算法相关的知识,才能可以写出效率更高的代码。而排序算法又是算法中非常基础的内容。

1142
来自专栏程序员互动联盟

【入门指导】学C语言一段时间了,还是一头雾水该咋办?

学C了一头雾水该怎么办?最简单的方法就是你再学一遍呗。俗话说熟能生巧,铁杵也能磨成针。 但是一味的为学而学,这个好像没什么卵用。为什么学了还是一头雾水,重点就在...

3887
来自专栏海天一树

我是如何成为一名少儿编程竞赛老师的

2017年9月,我以前一个同事问我能不能教他小孩Theo学习编程,因为以前在同一家公司时,我那同事经常带Theo去公司,我和Theo也认识,所以我答应了。

2294
来自专栏PHP在线

如何学好数据结构和算法

数据结构和算法是计算机科学中最重要的课程,作为一名Google的软件工程师,我经常看到一些求职者或刚毕业的学生,他们对于数据结构和算法的学习是远远不够的。这不是...

3496
来自专栏HansBug's Lab

2697: 特技飞行

2697: 特技飞行 Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 646  Solved: 393 [Su...

3267
来自专栏calmound

匈牙利算法

今天学习了下匈牙利算法,发现这个早在几个月前学过的知识已经忘记的一干二净了,记得当初学习的时候只是看书,看论文,现在要好好的总结下,防止以后再次忘记。 此次总结...

4427
来自专栏镁客网

3D打印出的这种“咖啡杯”状药丸,可定时定量发挥药效 | 黑科技

1590
来自专栏互扯程序

15个变态的Google面试题以及答案

在当前经济形势不景气的情况下,谷歌招聘新员工是一件令人振奋的事,特别是对那些在当前金融风暴中渴望找到安全港的年轻经理们和软件开发商们来说是个好消息。  

2051
来自专栏鸿的学习笔记

关于英语,也许你忽视了很多东西

这是葛传椝老先生对英语学习者的教导,通篇用易读的英文短文讲述了英语学习过程中的种种心得,其中“大都是英语语法书和英语修辞学书不曾提到的”,文短而词丰,言简而意赅...

1011

扫码关注云+社区

领取腾讯云代金券