Решаю задачу 1745 с тимуса.

Кратко: есть n <= 1000 каких-то скобочных последовательностей суммарной длиной не более 10000. нужно из них составить правильную максимальной длины.

Решаю так:

• Пусть есть какое-то множество последовательностей, такое, что кол-во левых и правых скобок в них одинаково (суммарно во всех)
• От каждой последовательности нам нужны две величины: минимальный баланс и суммарный баланс. То есть минимум по (кол-во откр. скобок) — (кол-во закр. скобок) на префиксе и эта же величина для всех строки.
• Отсортируем строки сначала по знаку суммарного баланса, затем, для тех, у которых знак неотрицательный, по невозрастанию минимального баланса, а для тех, у которых знак суммарного баланса отрицательный, по неубыванию.
• Будем делать динамику dp[i][j] — макс. длина последовательности, составленной из первых i строк в отсортированном порядке (возможно, не все используются), такой, что ее суммарный баланс равен j. Переходы можно делать вперед, добавляя очередную i+1 ю строку в этом порядке.

Казалось бы, все стандартно, сомнения только в третьем пункте, но и там, казалось бы, все очевидно. Однако получаю ва9 уже раз эдак в 10й, тщетно выискивая баги.

Буду благодарен за любую помощь!

http://pastebin.com/0C4VYbwJ

Ууупс. Нашел ошибку в решении. Неверно, что строки с отрицательным балансом надо так располагать =(

Просто, для отрицательных нужно считать не (минимальный баланс), а суммарный баланс — минимальный баланс.

Прошу прощения за этот флуд, но решил не прятать в черновики, вдруг кому пригодится.

Да, задача зашла.