题目传送门

6931. 访问数组中的位置使分数最大

题意
给你一个数组，初始你位于下标 1 处，你可以往后跳到数组任一下标，但不能往前跳。跳到哪个位置，即可获得下标对应的分数，但如果当前下标的数与跳之前下标的数奇偶性不同，那么你会失去分数 x。询问你能获得的最大分数？

思路
一眼动态规划，那么问题在于怎么规划？
我们贪心的考虑，要让分数最大肯定不能简单的选择奇数或者选择偶数，而是选择最大的跳，奇偶不同时仅存在分数 x 的亏损。那么对于每一个位置，我们都希望它是由前面某个位置跳过来，且能让当前位置取得最大值。又因为奇偶性的问题，所以我们可以记两个数 even 和 odd 来保存当前已经处理段结尾为偶数或者结尾为奇数时的最大值。当前数为偶数时更新 even， 当前数为奇数时更新 odd 。最终答案为 \(max(even, odd)\)

代码

#define ll long long
class Solution {
public:
	long long maxScore(vector<int>& a, int x) {
		int n = a.size();
		ll even, odd;
		even = a[0] + ((a[0] % 2 == 0) ? 0 : -x);
		odd = a[0] + ((a[0] % 2 == 0) ? -x : 0);
		for(int i = 1; i < n; ++ i){
			if(a[i] % 2){
				odd = a[i] + max(even - x, odd);
			}else{
				even = a[i] + max(even, odd - x);
			}
		}
		return max(odd, even);
	}
};