小美从n个编号为12n的糖果中选择任意多个糖果作为奖励每种编号糖果各一个第一行输入一个整数n表示糖果的数量第二行输入n个整数a1a2an其中ai表示编号为i的糖果的美味值1=n=500001=ai=10000输出为能获得的糖果美味值之和的最大值注意若选择了编号为i的糖果则不能选择编号为i-1i-2i+1i+2的四个糖果。用c++实现并注释一下代码

#include #include using namespace std; const int MAXN = 50005; int n, a[MAXN], dp[MAXN][2]; //dp[i][0/1]表示选择前i个糖果，第i个糖果被选/不被选的最大美味值 int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; dp[1][1] = a[1]; //第一个糖果被选的情况 for (int i = 2; i <= n; i++) { //不选第i个糖果 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); //选第i个糖果 dp[i][1] = max(dp[i - 2][0], dp[i - 2][1]) + a[i]; } cout << max(dp[n][0], dp[n][1]) << endl; return 0; }