P2669 [NOIP2015 普及组] 金币 提交 206.05k 通过 116.36k 时间限制 1.00s 内存限制 125.00MB 提交答案 加入题单

题目描述

有 $n$ 个硬币排成一个环，第 $i$ 个硬币有价值 $a_i$ ，其中 $1\le i\le n$。你可以选择一个硬币 $i$ ，同时拿走硬币 $i-1$ 和 $i+1$ （如果存在），然后得到 $a_i$ 的价值。

重复上述操作，直至只剩下一个硬币。请问最多能得到多少价值？

输入格式

第一行包含一个整数 $n$ ，表示硬币的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个硬币的价值。

输出格式

输出一个整数，表示最多能得到的价值。

数据范围

$1\leqslant n\leqslant10^5$,$1\leqslant a_i\leqslant10^4$

输入样例：

3
1 2 3

输出样例：

3

算法1

(模拟) $O(n^2)$

由于硬币是排成一个环的，所以我们将第一个硬币和最后一个硬币连成一个环，然后处理两种不同的情况：

- 拿走第 $i$ 个硬币，同时拿走 $i-1$ 和 $i+1$，然后将整个环缩小为 $n-3$ 个硬币；
- 拿走第 $i$ 个硬币，同时拿走 $i-1$ 和 $i+1$，然后将整个环缩小为 $n-2$ 个硬币。

在这两种情况中选择一个最优的即可。

时间复杂度

$O(n^2)$，其中 $n$ 是硬币的数量。

C++ 代码

算法2

(动态规划) $O(n^2)$

由于硬币是排成一个环的，所以我们将第一个硬币和最后一个硬币连成一个环，然后设 $f[i][j]$ 表示处理前 $i$ 个硬币，已经拿走了 $j$ 个硬币，所能得到的最大价值，则状态转移方程如下：

$$
f[i][j]=\max\left\{
\begin{aligned}
f[i-2][j-1]+a[i] && (i\ge2\ \&\&\ j\ge1) \\
f[i-1][j] && (i\ge1\ \&\&\ j\ge0)
\end{aligned}
\right.
$$

时间复杂度

$O(n^2)$，其中 $n$ 是硬币的数量。

C++ 代码

算法3

(动态规划) $O(n)$

观察上面的状态转移方程，我们发现 $f[i][j]$ 只依赖于 $f[i-2][j-1]$ 和 $f[i-1][j]$，因此我们可以使用滚动数组来优化空间复杂度。

时间复杂度

$O(n)$，其中 $n$ 是硬币的数量。

C++ 代码