NOIP2009道路游戏

题目描述
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路,马路上有 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 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失,小 新必须立刻在任意一个机器人工厂中购买一个新的机器人,并给新的机器人设定新的行走次 数。

以下是游戏的一些补充说明:

游戏从小新第一次购买机器人开始计时。
购买机器人和设定机器人的行走次数是瞬间完成的,不需要花费时间。
购买机器人和机器人行走是两个独立的过程,机器人行走时不能购买机器人,购买 完机器人并且设定机器人行走次数之后机器人才能行走。
在同一个机器人工厂购买机器人的花费是相同的,但是在不同机器人工厂购买机器 人的花费不一定相同。购买机器人花费的金币,在游戏结束时再从小新收集的金币中扣除,所以在游戏过 程中小新不用担心因金币不足,无法购买机器人而导致游戏无法进行。也因为如此, 游戏结束后,收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人 需要的花费,请你告诉小新,经过 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 个单位时间内,扣除购买机器人花费的金币之后,小新最多能收集到多少金币。

样例输入

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。

题解

其实这道题并不难,只是dp较为隐蔽,可以经过模拟样例来找规律;
样例:
2 3 2(表示有n段马路,m个单位时间,购买一个机器人可以走的路程)
1 2 3(在1——3秒内马路一的每秒价值)
2 3 4(在1——3秒内马路二的每秒价值)
1 2(在两家工厂购买机器人的费用)
不难发现我们只要在时刻1时在工厂2中购买一个机器人,那么获得马路2的价值2和三,然后继续购买机器人2,获得价值4,结束,获得总价值2+3+4=9,然后减去购买机器人的费用,9-4=5

不难发现,每次购买机器人,都是在选择后k秒最好的马路(工厂)

#难道是贪心?!

事实是这样吗?
再来个数据:

2 3 2
1 2 3
2 3 4
1 4

同样我们是获得了9个金币,但是却付出了8个金币的代价,最优解应该是1+2+3=6;6-1-1=4;

那么问题来了,既然贪心贪不了,该怎么做呢?

#动态规划!
建立一个f数组,f[i]表示在第i秒时能获得的最大价值。
那么我们可以获得一个方程转移
##F[i]=max(f[i],f[i-k]+ss-b[t]);
很好理解,ss就是路径上的金币总值,b[t]就是机器人的价格,i-k就是机器人的生产公司。。。

code:

这其实是90的暴力。。。

很明显吗O(n^3)不爆我**

其实我们不难发现,其实机器人走路是有

单调性的!!!

加个单调队列就满分了!!!
当然在很多OJ这样就够了。
洛谷这么打就AC了,vij也是

2 条评论
  1. O,what worry with markdown?

    1. #后面要加空格
      代码是cpp而不是c++

发表一条评论