本文主要是介绍AtCoder Beginner Contest 369 D - Bonus EXP 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：
https://atcoder.jp/contests/abc369/tasks/abc369_d
思路：
这道题为什么要用动态规划呢，其实，对于第i个怪物，我们有打与不打两种处理方式，而对于打，我们是获得两倍的经验值，还是一倍的经验值，与我们打了奇数只怪物还是打了偶数只怪物有关了，因此我们定义dp[i][0] 为前i只怪物总共打了偶数次，dp[i][1] 为前i只怪物总共打了奇数次，
而dp[i]又与dp[i-1]有关，如果i-1 次打了奇数次，第i次是偶数次，说明这个怪物打了，而且是偶数个打的要暴击为两倍，如果i与i-1 的奇偶性相同，则说明这只怪物没有打，获得0的经验值
代码实现：
#include<bits/stdc++.h>using namespace std;const int N=200010;int a[N];long long dp[N][2];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dp[1][0]=0;dp[1][1]=a[1];for(int i=2;i<=n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]+2*a[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]);}cout<<max(dp[n][0],dp[n][1])<<endl;return 0;
}
这篇关于AtCoder Beginner Contest 369 D - Bonus EXP 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
