3390: 假签到题？
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 43
[提交][状态][讨论版][命题人:]
题目描述
假设ACM工作室有n个人，将他们分别编号为1-n，现在小劉需要从他们之中挑选出一些人组成一队人员打比赛，在挑选时不能将相邻的两个人都选走。每个人都有自己的实力值，队伍的实力值等于队伍中最强那个人的实力值再加上队伍中的人数，现在需要求出这个最优解情况下的实力值为多少？
输入描述
第一行一个数字t，表示有t组测试样例（1<=t<=500）
接下里每组测试样例中
第一行一个数字n，表示一共有多少人数(1<=n<=100)
第二行有n个数字，分别表示每个人的实力值(每个人的实力值均在1到1000之间)
接下里每组测试样例中
第一行一个数字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
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版