Олимпиадный тренинг

Задача . Устранение массива


Задача

Темы:

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).

С массивом разрешается выполнять следующие два вида действий:

  1. Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).

  2. Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:

Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.

Определите, какое минимальное число монет требуется заплатить, чтобы превратить данный массив в пустой. Обратите внимание, что ответ всегда существует, потому что можно просто \(n\) раз применить первую операцию.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

Формат выходных данных
Выведите \(T\) целых чисел, каждое в своей строке — ответы на задачу для каждого набора входных данных в том порядке, в котором оны даны во вводе.

 

Примеры
Входные данныеВыходные данные
1 4
7
0 2 0 1 1 2 2
5
1 1 1 1 1
11
0 1 2 2 0 1 2 2 1 2 1
10
1 2 1 2 0 2 2 2 2 1
5
6
9
11

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python1
С++ Mingw-w641
Комментарий учителя