#PQJ1654x10227. QOJ 1654_10227
QOJ 1654_10227
标题: Travelling in the city - Problem - QOJ.ac
#10227. Travelling in the city
The problem was used in the following contests:
Problem Statement
亚当在一个相当狭窄的城市里旅行,这个城市可以被看作是数轴。轴上有 n 家餐馆,第 i(0≤i≤n−1) 家餐馆在数轴上 i+1 的位置。亚当从 0 开始,希望吃得越多越好,然后再回到 0。
亚当开始时体重为 1,我们假设他的体重将恰好增加他所摄入的数量。也就是说,吃了 a 单位的食物后,他的体重将增加 a。
为了在数轴上移动,亚当需要能量。亚当开始时有 x 的能量,他每移动一个单位,就需要花费与他当前体重相等的能量。亚当在任何时候都不能有负能量。换句话说,一旦亚当的能量耗尽,他就不能再移动了。
如果亚当在 [1,n] 中的整数位置 i,并且他之前没有进入餐厅 i−1,他可以走进去,吃恰好 ai−1 单位的食物。亚当是个好人,他不浪费粮食。
你必须保证亚当可以走回起点0。在此基础上,亚当想知道他能吃的最大总食物量。
Implementation Details
你应该包含 city.h,并实现如下过程:
int eat(int n, int x, int[] a)
- n: 餐馆的个数。
- x: 初始能量。
- a: 一个长度为 n 的数组,依次包含在每个餐馆进食会得到的食物量。
- 你实现的过程会被调用恰好一次。
- 你应该返回亚当能吃的最大总实物量。
Example
考虑如下调用:eat(5, 10, [1, 1, 1, 1, 1])
可以证明在这一情形下亚当最多能吃两单位食物,因此一个正确的程序应当返回 2。
一种可行方案为:从 0 走到 1,花费 1 行动力;进入餐馆 1 用餐,重量变为 2;从 1 走到 2,花费 2 行动力;进入餐馆 2 用餐,重量变为 3;从 2 走回 0,花费 6 行动力。剩余 1 行动力。
Constraints
0≤x≤106。
1≤n≤106。
对于每个 1≤i≤n,0≤ai≤x。
Subtasks
- (10 分)n≤12
- (20 分)n≤500,x≤1000
- (30 分)n≤5000
- (40 分)无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 第一行:n x
- 第二行:a[0] a[1] ⋯ a[n−1]
样例交互器以下列格式打印你的输出。
- 一行,你的返回值