Codeforces Round 923 (Div. 3) |
---|
Закончено |
Задана горизонтальная клетчатая полоса из $$$n$$$ клеток. В $$$i$$$-й клетке находится заряд краски величины $$$a_i$$$. Этот заряд можно:
Обратите внимание, что заряд можно использовать не более одного раза (то есть его нельзя использовать одновременно и влево и вправо). Допустимо, что клетка окажется покрашена более одного раза.
Какое минимальное количество раз заряд необходимо использовать, чтобы покрасить все клетки полосы?
В первой строке входных данных содержится целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных.
Каждый набор входных данных задаётся двумя строками. Первая из них содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество клеток в полосе. Вторая строка содержит $$$n$$$ положительных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ — величина заряда краски в $$$i$$$-й слева клетке полосы.
Гарантируется, что сумма значений $$$n$$$ в тесте не превосходит $$$1000$$$.
Для каждого набора входных данных выведите минимальное количество раз, сколько необходимо использовать заряды, чтобы покрасить все клетки полосы.
131121 122 121 222 231 1 133 1 231 3 171 2 3 1 2 4 272 1 1 1 2 3 1102 2 5 1 6 1 8 2 8 262 1 2 1 1 261 1 4 1 3 2
1 2 1 1 1 3 1 2 3 4 2 3 3
В третьем наборе входных данных примера достаточно использовать заряд из $$$1$$$-й клетки вправо, тогда он покроет обе клетки $$$1$$$ и $$$2$$$.
В девятом наборе входных данных примера нужно:
В одиннадцатом наборе входных данных примера нужно:
Название |
---|