Это сложная версия задачи. Разница между простой и сложной версиями задачи заключается только в ограничении на $$$n$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Дан массив целых чисел $$$a$$$ длины $$$n$$$.
Вы можете выполнять следующую двухшаговую операцию:
Найдите максимальное количество раз, которое можно применить данную операцию.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 800$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$800$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество раз, которое можно применить операцию из условия.
651 5 3 2 482 1 3 4 5 6 7 831 2 341 2 4 454 4 1 3 511
2 3 1 2 0 0
В первом наборе входных данных одна из возможных оптимальных последовательностей применения операций такая: $$$[ 1, 5, \color{red}{3}, \color{red}{2}, 4 ] \rightarrow [\color{red}{1}, \color{red}{5}, 4] \rightarrow [4]$$$.
В третьем наборе входных данных, одна из возможных оптимальных последовательностей применения операций такая: $$$[1, \color{red}{2}, \color{red}{3}] \rightarrow [1]$$$.
Название |
---|