Responsive image

问题 F: 假签到题?

问题 F: 假签到题?

时间限制: 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

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