598. Increasing Subsequences

[•Marius]

http://www.spoj.pl/problems/INCR/

ÃŽmi poate da cineva o idee la INCR? O altă idee decât „merge în două zile în O(N! * N²)”.

[•wefgef]

Merge o dinamica dubioasa:

O "stare" ti-e determinata de lungimea unei permutari, precum si de cel mai mic ultim element al unei secvente crescatoare de lungime 1, cel mai mic ultim element al unei secvente crescatoare de lungime 2, ... cel mai mic ultim element al unei secvente crescatoare de lungime B-1. Pentru B = 5, ai N^5 stari. Cred ca poti sa scoti recurenta in O(1) daca te gandesti putin.

Asta e prima idee care mi-a venit in minte, asa ca s-ar putea sa nu fie tocmai cea mai buna .