|
Titlul: 245 Avere Scris de: Filip Cristian Buruiana din Aprilie 28, 2006, 14:41:42 Aici puteţi discuta despre problema Avere (http://infoarena.ro/problema/avere).
Titlul: Răspuns: 245 Avere Scris de: Vlad Eugen Dornescu din Ianuarie 08, 2011, 15:09:32 Salut, am o solutie in O(S^3) care ia maxim 50 puncte (cu tot cu reconstituire).Am nevoie de un hint pentru modul in care reprezint tabloul de PD (si complexitate mai mica, O(S^2) ma gandesc).
Eu am DP[ i ][ j ] - nr.de posibilitati, a.i sa formez suma i si cu ultimul element ales j. Solutia mea e suma de pe linia n. Mersi. :) L.E : Am citit si solutia oficiala de la 'Avere - clasa a X-a, ONI 2005'.Problema e ca nu inteleg ce inseamna c[ i ][ j ] la ei, pentru ca e scrisa doar o recurenta, fara a fi explicata starea. :'( Titlul: Răspuns: 245 Avere Scris de: Paul-Dan Baltescu din Ianuarie 08, 2011, 17:36:32 Merge sa reduci recurenta la dinamica ta la O(1) folosind sume partiale.
|