Responsive image

问题 3390 --假签到题？

3390: 假签到题？

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 49
[提交][状态][讨论版][命题人:]

题目描述

假设ACM工作室有n个人，将他们分别编号为1-n，现在小劉需要从他们之中挑选出一些人组成一队人员打比赛，在挑选时不能将相邻的两个人都选走。每个人都有自己的实力值，队伍的实力值等于队伍中最强那个人的实力值再加上队伍中的人数，现在需要求出这个最优解情况下的实力值为多少？

输入描述

第一行一个数字t，表示有t组测试样例（1<=t<=500）
接下里每组测试样例中
第一行一个数字n，表示一共有多少人数(1<=n<=100)
第二行有n个数字，分别表示每个人的实力值(每个人的实力值均在1到1000之间)

输出描述

输出最优解情况下的实力值

样例输入

4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 4 5
9
17 89 92 42 29 92 14 70 45

样例输出

7
6
10
97

提示

在第一个测试样例中，将1号和3号挑走，求出该情况下队伍的实力值为5+2=7，为最大值，所以输出7

在第二个测试样例中，将1号和3号挑走，求出该情况下队伍的实力值为4+2=6，为最大值，所以输出6

在第三个测试样例中，将2号，4号，6号，8号，10号挑走，求出该情况下队伍的实力值为5+5=10，为最大值，所以输出10

来源

23软3刘震峰 

[提交][状态]
ACM算法攻关部