Привет CodeForces.
Я не буду давать ссылку на задачу и даже объяснять условия задачи, потому-что эту задачу можно решить более легким способом. Но я хочу реализовать свою идею, но есть сложности в реализации и прошу вас помочь разобраться с этими сложностями.
В задаче требуется пересчитывать динамику
таким образом
Думаю есть способ быстро считать dp[i] = max(dp[j - 1] + (mx[j] - mn[j])) для 1 <= j < i
mx[j] -> максимум от j до i
mn[j] -> минимум от j до i
Заранее большое спасибо!
Из формулы следует что dp[i] > = dp[i - 2] + mx[i - 1] - mn[i - 1] > = dp[i - 2] для любого i. Но если j2 > j1 и dp[j2 - 1] > = dp[j1 - 1], то dp[j2 - 1] + mx[j2] - mn[j2] > = dp[j1 - 1] + mx[j1] - mn[j1], значит dp[i] = max(dp[i - 2] + mx[i - 1] - mn[i - 1], dp[i - 3] + mx[i - 2] - mn[i - 2]), то есть на каждом шаге достаточно проверять только значения j = i - 1 и j = i - 2, иначе j можно увеличить на 2 и выражение под максимумом не уменьшится.
Что-то вроде этого?
Можешь так попробовать —
rep(i, 1, n){ int mx = -inf, mn = inf, cnt = 100; per(j, i, 1){ mx = max(mx, a[j]), mn = min(mn, a[j]); int val = dp[j — 1] + (mx — mn); if (val > dp[i]) cnt = 100, dp[i] = val; else --cnt; if (cnt == 0) break; } }
В худшем случае квадрат но интересно, зайдет или нет :)
А вообще проверь dp[i], не переполняешься ли ты.
И решение выше, которое тебе описали — с ним все хорошо.
Просто то, что ты получаешь WA — это не аргумент.
Кажется ваше утверждение неверное
достаточно проверять предыдущий елемент, потому что mx — mn >= 0, из чего следует, что значения dp будут неубывающей последовательностью.
это идея получает WA
тогда можно хранить значения, на которые ми пересчитываем dp, в дереве отрезков и пересчитывать их за log(n)
Очень интересно как это делать.
Можете показать?
Будем хранить в дереве отрезков структуру вида(max, min, val) — где max i min — максимум и минимум для текущих значений этого dp, a val — значение этого dp. В каждой вершине будем держать максимальную по сумме значений структуру на этом отрезке. На каждой итерации будем обновлять максимум и минимум на префиксе с помощью массовых запросов, и добавлять в дерево значение dp, которое будет равняться сумме всех значений в структуре.
Вау)
Для меня это нереальная реализация, потому-что я не умею делать эти операции деревом отрезков.
Может подскажете как делать???
Update(l, r, x) for (int i = l; i <= r; i++) mx[i] = max(mx[i], x), mn[i] = min(mn[i], x);
Круто будет если вообще код оставите )
Ну проблем с хранением структур в дереве отрезков не должно возникнуть, я думаю.
А вот суть массовых запросов состоит в том, чтобы не спускаться вниз по всех вершинах, для каждой вершины делаем обещание, если нам надо обновить все вершины в этом поддереве. Потом при спуске в какую-то вершину мы обновляем в ней информацию и проталкиваем обещание двум детям этой вершины.
А добавление значение — то же самое, если б мы заменяли нейтральный елемент (например (-inf,-inf,-inf) ) на новое значение.
По сути все детали я описал, надеюсь, понятно.
Nevermind, i was wrong :D. Even though the optimal j's are increasing, the recurrence function might have several local maximum values.
Попробуй такое:
Возьмем первый слева от i элемент больше a[i], назовем jmax. Возьмем первый слева от i элемент меньше a[i], назовем jmin. Тогда j это что-то из {i, jmax + 1, jmin + 1).
I think I have a really nice idea, but I'm not sure it works. I'll try implement it, but please provide a link to reassure the correctness. I really want to see with my own eyes that it works. The task is very interesting because at first glance it seems just some usual dp, and then you have no idea how to continue the optimization.
:)
Ok, thanks. I see that I once read the task(actually during the contest) but didn't upsolve it. So before implementing my current idea, I took a look at the editorial because I saw that a lot of people solved it and I thought (and I was right) that I miss something and my solution is overcomplicated. I guess that since you asked about it on forum you've already read the editorial and didn't understand. The key observation is that every segment in the optimal solution would consist of a monotonic sequence(that is either increasing, either decreasing). Why is that? You can prove it easily by considering a point i inside the segment that has a[i — 1] > a[i] < a[i + 1] or a[i — 1] < a[i] > a[i + 1]. For simplicity, let's suppose we already proved the statement for smaller lengths and there is at most one such point. if you cut the string before i, or immediately after i, you'll get a better total cost. So now everything that needs to be done is to use this observation. For that matter, you can just consider the cost of some interval [i, j] as |a[i] — a[j]| because in any such interval, |a[i] — a[j]| <= cost (so you won't get a solution better than the optimal one) and the optimal one will be taken into consideration (because the intervals that make up the partition are monotonic so the cost in that case is going to be exactly |a[i] — a[j]|). For doing that it is enough to use the recurrence dp[i] = max (dp[j] + a[i] — a[j + 1], dp[j] + a[j + 1] — a[i]) (and that is from a similar way of thinking, because max (x — y, y — x) = |x — y| so, again, you won't miss the solution). Using this reccurence, we get O(N) complexity.