有N只怪兽,第i只怪兽的体力为A[i],需要按编号从小到大的顺序依次处理,对于每只怪兽可以选择打或不打,如果不打,经验值不变;如果打,将获得等同于怪兽体力的经验值。另外,对于第偶数次打的怪兽,经验值翻倍。求能获得的最大经验值。
1<=N<=2E5; 1<=A[i]<=1E9
分析:获得的经验跟奇偶性有关,设dp0[i]表示前i只怪兽打了偶数只的答案,dp1[i]表示前i只怪兽打了奇数只的答案。根据打或不打,以及奇偶性进行递推。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int N;
std::cin >> N;
std::vector<int> A(N+1);
for (int i = 1; i <= N; i++) {
std::cin >> A[i];
}
std::vector<i64> dp0(N+1), dp1(N+1);
dp0[0] = 0;
dp1[0] = -1E18;
for (int i = 1; i <= N; i++) {
dp0[i] = std::max(dp0[i-1], dp1[i-1] + 2 * A[i]);
dp1[i] = std::max(dp1[i-1], dp0[i-1] + A[i]);
}
std::cout << std::max(dp0[N], dp1[N]) << "\n";
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:std,怪兽,dp1,dp0,Bonus,int,EXP,经验值,abc369D
From: https://www.cnblogs.com/chenfy27/p/18450409