B4135 [信息与未来 2014] 取数题解

# B4135 [信息与未来 2014] 取数 题解

**免责声明:如遇雷同，纯属巧合**

### 1. 读题

- 题意：在一个序列中任取若干个数，取数规则为每次取相邻的 2 个数，且不能取多于 2 个连续的数，使和最大。

- 样例解释（我一开始就没弄明白）：$13 \hspace{1mm}2\hspace{1mm}17 \hspace{1mm}14\hspace{1mm}8\hspace{1mm}16$ 每次取相邻的 2 个数，且不能取多于 2 个连续的数，使和最大。

- 第一次：$13 \hspace{1mm}2\hspace{1mm}\left [ 17 \hspace{1mm}14\right ]\hspace{1mm}8\hspace{1mm}16\hspace{3mm}和为0+17+14=31$。

- 第二次：$13 \hspace{1mm}2\hspace{1mm}17 \hspace{1mm}14\hspace{1mm}\left [ 8\hspace{1mm}16\right ]\hspace{3mm}和为31+8+16=43$。

----

### 2. 使用动态规划解决

- 动态转移方程推导

- **情况一**选择第 $i$ 个元素：若选择第 $i$ 个元素，就不能选取第 $i-1$ 个元素，就需要考虑前 $i-3$ 个元素的情况。此时选取的元素和为 $dp[i-3]+a[i-1]+a[i]$。其中，`dp[i-3]` 是考虑前 i-3 个元素的最大和，`a[i-1]` 和 `a[i]` 是当前选择的两个部相邻元素。

- **情况二**不选第 $i$ 个元素：若不选第 $i$ 个元素，那么最大元素和就同等于考虑前 $i-1$ 个元素时的最大元素和，即 `dp[i-1]`。因为不选第 $i$ 个元素，所以问题规模就缩小到了前 $i-1$ 个元素
- 因此，状态转移方程为 $dp[i]=max(dp[i-1],dp[i-3]+a[i-1]+a[i]);$。

----

### 3. 代码片段分析

由于此题只需要输入就可以**直接套状态转移方程**，就不给予分析了（一前面讲的是够详细了，二是我只能讲成这样了）。

----

### 4. AC 代码

如上所述，没必要出示代码，但如果你是[这种情况](https://www.luogu.com.cn/record/210200822)，我只能引用一句 OI 界的名言：

> 十年 OI 一场空，不开 long$\hspace{1mm}$long 见祖宗。

----

~~我写的第三篇题解，前两篇都在我修改后不接受题解了（简称：**没审过，现在不接受了**）~~  
有问题请指出，求过

正在渲染内容...

B4135 [信息与未来 2014] 取数 题解

B4135 [信息与未来 2014] 取数题解