|
Titlul: 598. Increasing Subsequences Scris de: Marius Stroe din Septembrie 05, 2008, 13:11:59 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! * N2)”. :) Titlul: Răspuns: 598. Increasing Subsequences Scris de: Andrei Grigorean din Septembrie 06, 2008, 17:57:09 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 :). |