#2202. Travelling in the city

    ID: 2202 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1654来源:qoj.ac数据:公开样例动态规划

Travelling in the city

Travelling in the city

题目描述

标题: Travelling in the city - Problem - QOJ.ac

#10227. Travelling in the city

Statistics

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

  1. (10 分)n≤12
  2. (20 分)n≤500,x≤1000
  3. (30 分)n≤5000
  4. (40 分)无特殊限制。

Sample Grader

样例交互器以下列格式读取输入。

  • 第一行:n x
  • 第二行:a[0] a[1] ⋯ a[n−1]

样例交互器以下列格式打印你的输出。

  • 一行,你的返回值

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 10
1 1 1 1 1
2