Блог пользователя Whimsical_HITMAN

[Help] LIS type of problem.
Автор Whimsical_HITMAN, история, 13 месяцев назад, По-английски

https://www.spoj.com/problems/ONEXLIS/

i have been trying to solve the problem for a long time...but couldnt come up with a proper approach... My approach(ig wrong) : when we consider a sequence to be lis, the elements before the last element must have lds(longest strictly decreasing subsequence) > 1; however im unable to implement the idea; any help would be appreciated.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Firstly without loss of generality, we can assume that $$$0 \le a_i \le n - 1$$$, by coordinate compression.

Let's try fixing the one pair that is out of order in the subsequence. Define $$$l_x, r_x$$$ to be the longest increasing sequence ending at index $$$x$$$ and the longest increasing sequence starting from index $$$y$$$ respectively. These values can be computed for all $$$x$$$ using a segment tree in one pass. Then the answer to the problem is $$$\max_{i < j, a[i] > a[j]} l_i + r_j$$$. Iterating over $$$j$$$, this is also doable using a segment tree.

→ Ответить