#P29. 【IOI2014】Holiday

【IOI2014】Holiday

健佳正在制定下个假期去台湾的游玩计划。在这个假期,健佳将会在城市之间奔波,并且参观这些城市的景点。

在台湾共有 $n$ 个城市,它们全部位于一条高速公路上。这些城市连续地编号为 $0$ 到 $n - 1$。对于城市 $i$ ($0 < i < n - 1$) 而言,与其相邻的城市是 $i - 1$ 和 $i + 1$。但是对于城市 $0$,唯一与其相邻的是城市 $1$。而对于城市 $n - 1$,唯一与其相邻的是城市 $n - 2$。

每个城市都有若干景点。健佳有 $d$ 天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天,健佳可以选择去一个相邻的城市,或者参观所在城市的所有景点,但是不能同时进行。即使健佳在同一个城市停留多次,他也不会去重复参观该城市的景点。请帮助健佳策划这个假期,以便能让他参观尽可能多的景点。

任务

请实现函数 findMaxAttraction,以计算健佳最多可以参观多少个景点。

  • findMaxAttraction(n, start, d, attraction)
    • $n$: 城市数。
    • start: 起点城市的编号。
    • $d$: 假期的天数。
    • attraction: 长度为 $n$ 的数组;attraction[i] 表示城市 $i$ 的景点数目,其中 $0 \leq i \leq n - 1$。
    • 该函数应返回健佳最多可以参观的景点数。

子任务

在所有的子任务中,有 $0 \leq d \leq 2n + \lfloor n / 2 \rfloor$。而且,每个城市中的景点数都是非负整数。

子任务分值$n$各城市景点数的最大值起点城市
17$2 \leq n \leq 20$$10^9$无限制
223$2 \leq n \leq 100000$$100$城市 $0$
317$2 \leq n \leq 3000$$10^9$无限制
453$2 \leq n \leq 100000$$10^9$无限制

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现上述的函数,其命名与接口需遵循下面的要求。你还要在该文件中包含头文件holiday.h。

注意,计算的结果可能会很大,所以函数 findMaxAttraction 的返回值类型是一个64位整数。

long long int findMaxAttraction(int n, int start, int d, int attraction[]);

评测方式

评测系统需要读入如下格式的输入数据:

  • 第 $1$ 行: $n$, start, $d$。
  • 第 $2$ 行: $\text{attraction[0]}, \dots, \text{attraction[n-1]}$。

评测系统将会输出 findMaxAttraction 的返回值。

交互式类型的题目怎么本地测试

时间限制:$5\texttt{s}$

空间限制:$64\texttt{MB}$

下载

样例及测评库下载