A27734. 体验积分值 (point)卡卡西和小朋友们做完了烧脑的数字游戏，决定放松一下，他们来到了万达乐园，乐园中有很多的游玩项目，每玩一个项目就能获取一定的体验积分，不同的项目产生不同的体验积分，假设乐园所有的游乐项目正好排成一排，并且游客们不能游玩任意相邻的两个项目，那么卡卡西如何挑选游玩项目，使得这次万达行他能获得最多的体验积分值呢。输入输入共两行，第一行是一个正整数 n ，表示万达乐园的游乐项目数…
填空题
中等
知识点
题目描述
体验积分值 (point)
卡卡西和小朋友们做完了烧脑的数字游戏，决定放松一下，他们来到了万达乐园，乐园中有很多的游玩项目，每玩一个项目就能获取一定的体验积分，不同的项目产生不同的体验积分，假设乐园所有的游乐项目正好排成一排，并且游客们不能游玩任意相邻的两个项目，那么卡卡西如何挑选游玩项目，使得这次万达行他能获得最多的体验积分值呢。
输入
输入共两行，第一行是一个正整数 n ，表示万达乐园的游乐项目数。第二行是 n 个用空格隔开的正整数，分别表示每个游乐项目的体验积分值。
输出
只有一个正整数，为最多的体验积分值。
样例 1
输入
5
3 10 8 20 21
输出
32
样例1说明
一共 5 个游玩项目，卡卡西选择第一个、第三个和第五个游玩，可共可获得 3+8+21=32 的体验积分值。
样例 2
输入
5
3 17 8 20 21
输出
38
样例说明
一共 5 个游玩项目，卡卡西选择第二个和第五个游玩，可共可获得
17+21=38 的体验积分值。
数据范围
5 ≤ n ≤ 1000 1 ≤每个游玩项目体验积分值≤ 500
参考答案
#include<bits/stdc++.h>
using namespace std;
int n,a[1010],dp[1010];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[1]=a[1]; //初始化
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-2]+a[i],dp[i-1]); //动态转移方程
}
cout<<dp[n];
return 0;
}
上一题
下一题