Codeforces Round 975 (Div. 2) |
---|
Закончено |
Дан массив целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$.
Вы можете раскрасить некоторые элементы массива в красный цвет, но при этом в нем не должно оказаться двух соседних красных элементов (т.е. для $$$1 \leq i \leq n-1$$$ хотя бы один из $$$a_i$$$ и $$$a_{i+1}$$$ должен не быть красным).
Ваш счет — это максимальное значение красного элемента плюс количество красных элементов. Найдите максимальный счет, который вы можете получить.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длина массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — заданный массив.
Для каждого набора входных данных выведите одно целое число — максимально возможный счет, который можно получить, раскрасив некоторые элементы в красный цвет в соответствии с условием.
435 4 534 5 4103 3 3 3 4 1 2 3 4 5917 89 92 42 29 92 14 70 45
7 6 10 97
В первом наборе входных данных вы можете раскрасить массив следующим образом: $$$[\color{red}{5}, 4, \color{red}{5}]$$$. Ваш счет составит $$$\max([5, 5]) + \text{size}([5, 5]) = 5+2 = 7$$$. Это максимальный счет, который вы можете получить.
Во втором наборе входных данных вы можете раскрасить массив следующим образом: $$$[\color{red}{4}, 5, \color{red}{4}]$$$. Ваш счет составит $$$\max([4, 4]) + \text{size}([4, 4]) = 4+2 = 6$$$. Это максимальный счет, который вы можете получить.
В третьем наборе входных данных вы можете раскрасить массив следующим образом: $$$[\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 4, \color{red}{5}]$$$. Ваш счет составит $$$\max([3, 3, 4, 3, 5]) + \text{size}([3, 3, 4, 3, 5]) = 5+5 = 10$$$. Это максимальный счет, который вы можете получить.
Название |
---|