2017合肥市第 34 届青少年信息学（计算机）奥林匹克竞 赛小学组试题-体验积分值(point)
任务描述：为了解决卡卡西在万达乐园如何选择游玩项目以获得最多体验积分的问题。
问题分析：给定n个游乐项目的体验积分值（n≤1000），不能选择相邻的两个项目。需要找出一种选择方式使得总积分最大。
输入格式：第一行为正整数n表示游乐项目数量；第二行有n个正整数表示每个项目的体验积分值。
输出要求：输出一个正整数表示最大可能的体验积分值。
解决方法：使用动态规划算法。定义两个变量excl和incl分别表示到当前项目时排除和包含当前项目的最大积分值。通过遍历所有项目更新这两个变量以得到最终的最大积分数值。
示例说明：
样例1中选第1、3、5个项目得到3+8+21=32分；
样例2中选第2、5个项目得到17+21=38分；
代码实现则通过循环遍历每个项目并更新excl和incl的值来求解最大积分。
4 、体验积分值 (point)
卡卡西和小朋友们完成了复杂且富有挑战性的数字谜题，并决定选择短暂休息以缓解疲劳后前往万达广场。
乐园内拥有丰富多样的游玩项目，在参与每个游玩项目即可获得一定的体验积分。不同类别间存在显著差异。
所有游乐项目会产生不同的体验积分。假设该主题公园的所有游乐项目按顺序排列成一行，并且游客
我们不能同时选择任何两个相邻的项目。那么卡卡西应该如何合理安排游玩项目以此次万达项目的安排为例。
行他能获得最多的体验积分值呢。
输入： 输入共两行，第一行是一个正整数 n ，表示万达乐园的游乐项目数。第
二行是 n 个用空格隔开的正整数，分别表示每个游乐项目的体验积分值。
输出：只有一个正整数，为最多的体验积分值。
样例 1 ：
输入：（ point.in ）
5
3 10 8 20 21
输出：（ point .out ）
32
样例说明：一共 5 个游玩项目，卡卡西选择第一个、第三个和第五个游玩，可共
青少年信息学奥林匹克竞赛
小学组试题
可获得 3+8+21=32 的体验积分值。
样例 2 ：
输入：（ point.in ）
5
3 17 8 20 21
输出：（ point .out ）
38
样例说明：一共 5 个游玩项目，卡卡西选择第二个和第五个游玩，可共可获得
17+21=38 的体验积分值。
数据范围 :
5 ≤ n ≤ 1000 1 ≤每个游玩项目体验积分值≤ 500
#include <iostream>
using namespace std;
int maxSum(int *arr, int size)
{
if(size<=0)
return 0;
else if(size ==1)
return arr[0];
int excl = 0, incl = arr[0];
int excl_new;
for(int i = 1; i<size; ++i)
{
excl_new = (excl>incl)?excl:incl;
incl = excl + arr[i];
excl = excl_new;
}
return (incl>excl)?incl:excl;
}
int main()
{
int array[] = {3 ,17, 8 ,20 ,21};
cout<<maxSum(array, 5)<<endl;
}
AI助手