题解：P14746 下午茶时光
_burbur_
·
·
题解
题目分析
本题要求我们在给定的点心序列中选择若干区间组合，每个组合中只取奇数编号的点心，且每个新组合的开始需要花费固定的代价 C。我们需要最大化总收益。
状态定义
设 dp[i][0] 表示考虑前 i 个点心，且第 i 个点心不被选中时的最大收益。
设 dp[i][1] 表示考虑前 i 个点心，且第 i 个点心被选中且在组合内为奇数位置（即被吃掉）时的最大收益。
设 dp[i][2] 表示考虑前 i 个点心，且第 i 个点心被选中且在组合内为偶数位置（即不被吃掉）时的最大收益。
状态转移方程
对于 dp[i][0]
第 i 个点心不被选中，那么前 i-1 个点心可以处于任意状态：
dp[i][0]=\max(dp[i−1][0], dp[i−1][1],dp[i−1][2])
对于 dp[i][1]
第 i 个点心被选中且是奇数位置（被吃掉），有两种情况：
开始一个新的组合：那么第 i-1 个点心不能是同一个组合的一部分（只能是 dp[i-1][0] 状态），需要花费 C 来开始新组合：
收益：val。
val=dp[i−1][0]+a[i]−C
延续上一个组合：那么第 i-1 个点心必须是偶数位置（dp[i-1][2] 状态），这样第 i 个点心的编号才能是奇数：
val=dp[i−1][2]+a[i]
取两种情况的最大值：
对于 dp[i][2] 第 i 个点心被选中且是偶数位置（不被吃掉），那么它必须属于某个已开始的组合，且前一个点心必须是奇数位置：
dp[i][2]=dp[i−1][1]
初始条件
$dp[0][1] = dp[0][2] = -\infty$（不可能的状态）
最终答案
考虑完所有 $n$ 个点心后，取三种状态的最大值：
$$ans=\max(dp[n][0],dp[n][1], dp[n][2]) $$
时间复杂度
状态数为 $O(n)$，每个状态的转移是 $O(1)$，总时间复杂度为 $O(n)$，可以处理 $n \leq 3 \times 10^5$ 的数据范围。
**Code**
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll n, c;
cin >> n >> c;
vector<ll> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
vector<ll> dp0(n + 1), dp1(n + 1), dp2(n + 1);
dp0[0] = 0;
dp1[0] = dp2[0] = -1e18;
for(int i = 1; i <= n; i++){
// 不选第 i 个
dp0[i] = max({dp0[i - 1], dp1[i - 1], dp2[i - 1]});
// 选第 i 个作为奇数位置（吃）
dp1[i] = max(dp0[i - 1] + a[i] - c, dp2[i - 1] + a[i]);
// 选第 i 个作为偶数位置（不吃）
dp2[i] = dp1[i - 1];
}
cout << max({dp0[n], dp1[n], dp2[n]}) << endl;
return 0;
}
```