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

#include #include #include

using namespace std;

int main() { int n; cin >> n; vector a(n+5, 0); vector dp(n+5, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; } dp[1] = a[1]; dp[2] = max(a[1], a[2]); for (int i = 3; i <= n; i++) { dp[i] = max(dp[i-2]+a[i], dp[i-3]+a[i]); } cout << dp[n]; return 0; }