题解：P14746 下午茶时光
SuyctidohanQ · · 题解
我们先来理解一下题意：
- 可以选若干段连续区间。
- 每个区间内，奇数编号（从
1 开始）的点心被吃，偶数编号的不吃。 - 每个新区间开始需要花费
C 。 - 目标是最大化总甜蜜值。
哎......？分组问题？考虑 DP。
我们需要知道当前位置的奇偶性，设：
转移：
- 不选当前点心：
f_{i,0}=\max\{f_{i-1,0},f_{i-1,1},f_{i-1,2}\} 。 - 开始新区间或延续奇数位置：
f_{i,1}=\max\{f_{i-1,0} - C + a_i, f_{i-1,2} + a_i\} 。 - 延续偶数位置（不吃，不获得
a_i ）：f_{i,2}=f_{i-1,1} 。
初始化：