Sto provando a risolvere il problema (velox) ma non riesco a capire perchè certi miei output siano errati. Quali sono i vincoli da rispettare, oltre al fatto che gli archi devono essere necessariamente di peso maggiore? Qualcuno ha risolto correttamente questo esercizio?
Il vincolo è solo quello. Io l’ho risolto in dinamica topdown, però con una piccola variazione da quella standard (perlomeno standard per me) che sarebbe andata oltre i limiti di memoria.
Se vuoi puoi postare il codice e vedere dove sbagli.
Il codice è il seguente:
int visita(int corrente, int velocita)
{
//cout<<"visito la citta "<<corrente<<" vel = "<<velocita<<endl;
if (sol[corrente] != -1 ) return sol[corrente];
int massimo = 0;
for(int i=0;i< M;i++)
if (archi[i][0] == corrente && archi[i][2] > velocita)
massimo = max( massimo , visita( archi[i][1] , archi[i][2] ) + 1 );
return sol[corrente] = massimo ;
}Non puoi salvarti la soluzione avendo come informazione solo il nodo corrente, ma devi conoscere anche il nodo da cui stai arrivando.
O più semplicemente non ti salvi le soluzioni sui nodi ma sugli archi! 
La miglior soluzione sul nodo X dipende anche da quale nodo Y provengo (come ha detto Lawliet) tuttavia la soluzione migliore percorrendo l’arco E è univocamente determinata, infatti dipende solo dall’arco E e dai suoi sottoproblemi 
L’ho risolto anch’io così ma non volevo aiutarlo troppo 
1 Mi Piace
Ooopss 
Non sono mai stato capace a dare consigli :v
L’altra soluzione ovviamente funzionava, ma per grossi input sforava i limiti di tempo, quindi devo applicare la Programmazione Dinamica.
L’ho modificato in questo modo, ma non riesco a trovare l’errore:
int visita(int arco)
{
if (sol[arco] != -1) return sol[arco];
int massimo = 0;
for(int i=1;i<=M;i++)
if (archi[i][0] == archi[arco][1] && archi[i][2] > archi[arco][2])
massimo = max( massimo , visita(i) + 1 );
sol[arco] = massimo;
return massimo;
}
int main()
{
cin>>N>>M;
archi[0][2] = -1;
for(int i=1;i<=M;i++) cin>>archi[i][0]>>archi[i][1]>>archi[i][2];
int massimo = 0;
fill(sol,sol+M,-1);
for(int i=0;i<N;i++)
{
archi[0][1] = i;
massimo = max( massimo, visita(0) );
sol[0] = -1;
}
cout<<massimo<<endl;
return 0;
}Innanzi tutto la fill chiamata in quel modo non ti setta sol[M] a -1, perché arrivando a sol+M si ferma.
Per il resto in teoria sta bene. Io l’ho risolto diversamente, ma l’idea è quella. La tua implementazione è effettivamente un po’ strana ma dovrebbe funzionare.
Quanti punti totalizza questa soluzione (dopo aver corretto la fill magari)?
Devi comunque trovare una soluzione migliore di questa, dato che hai come complessità O(M^2). Infatti per ogni arco nella DP scorri tutti gli archi (che sono M).
Vero anche questo.
(PS: Complimenti per essere nella squadra delle IOI 
)
1 Mi Piace