Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 598. Increasing Subsequences  (Citit de 9904 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : 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)”. Smile
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : 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 Smile.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines