Решаю задачу 1745 с тимуса.
Кратко: есть n <= 1000 каких-то скобочных последовательностей суммарной длиной не более 10000. нужно из них составить правильную максимальной длины.
Решаю так:
- Пусть есть какое-то множество последовательностей, такое, что кол-во левых и правых скобок в них одинаково (суммарно во всех)
- От каждой последовательности нам нужны две величины: минимальный баланс и суммарный баланс. То есть минимум по (кол-во откр. скобок) — (кол-во закр. скобок) на префиксе и эта же величина для всех строки.
- Отсортируем строки сначала по знаку суммарного баланса, затем, для тех, у которых знак неотрицательный, по невозрастанию минимального баланса, а для тех, у которых знак суммарного баланса отрицательный, по неубыванию.
- Будем делать динамику dp[i][j] — макс. длина последовательности, составленной из первых i строк в отсортированном порядке (возможно, не все используются), такой, что ее суммарный баланс равен j. Переходы можно делать вперед, добавляя очередную i+1 ю строку в этом порядке.
Казалось бы, все стандартно, сомнения только в третьем пункте, но и там, казалось бы, все очевидно. Однако получаю ва9 уже раз эдак в 10й, тщетно выискивая баги.
Буду благодарен за любую помощь!
Ууупс. Нашел ошибку в решении. Неверно, что строки с отрицательным балансом надо так располагать =(
Просто, для отрицательных нужно считать не (минимальный баланс), а суммарный баланс — минимальный баланс.
Прошу прощения за этот флуд, но решил не прятать в черновики, вдруг кому пригодится.
Да, задача зашла.
А может просто расположить строки по убыванию минимального баланса?
хм. мне чуть менее понятно почему это работает.
UPD. бред, можно не читать. Контрпример cerealguy ниже.
Пусть у нас есть ответ, состоящий из каких-то строк, тогда эти строки можно менять местами как угодно, кроме случаев, в которых образуется минимальный баланс у всей строки отрицательный, а это значит что мы можем поставить просто все строки с положительным минимальным балансом вначало а потом поставить с отрицательным минимальным балансом, тогда общий баланс так и останется равным нулю, а минимальный баланс будет неотрицательным (ну, если мы в динамике проверяем чтобы не уходить в минус). Поэтому в динамике нам важно вначале обработать с положительным минимальным балансом, а потом с отрицательным.
Но нам ведь еще надо, чтобы строки с отрицательным минимальным балансом не поднимались обратно в плюс, иначе их нужно поставить не в самый конец.
типа там (мин баланс, сум. баланс): (-100, -1) (-50, -50) (-49, -49)
мы это расположим как (-49, -49) (-50, -50) (-100, -1). И будет не очень. а если, как в первом случае, будет ок.
Я чего-то не понимаю?
как сортировать?
Да, не прав, сори.
Well I am stuck on this problem, as you mentioned in last paragraph " Simply, for negative ones, it is necessary to consider not (the minimum balance), but the total balance — the minimum balance." I had the same problem I did accordingly and submitted and it got Accepted but I still doesn't understand how we come up with this relation. I have seen previously also that whenever we have two or more variables we add or subtract them linearly with their constant factor as 1. like If we have two variables here as total balance and minimum balance then we simply did total balance — minimum balance. But how do we reach to this. Yours is only blog on net I can find about this problem.
Remove the substring (both easy and hard version) will help u to understand it better. In comments ppl have described the solution.