Trampolino elastico. Help me :(

[xCoder]

Ragazzi come posso aumentare le prestazioni del mio programma? Il problema è “Trampolino Elastico” 

Il mio codice è :

#include <iostream>


#include <vector>


#include <fstream>


using namespace std ;





typedef long long int lli ;


ifstream in("input.txt");


ofstream out("output.txt");





lli n ;


const int dim = 100000;





lli v[dim];





lli max_ = dim ;








void calcola(int k,lli t)


{


    if (t>=max_ || max_==1) return;


    if (k == n)


    {


        max_ = min(max_,t);


        return ;


    }


    for (int j = 1 ; j<=v[k] ; j++)


        if (k+j <=n)


            calcola(k+j,t+1);


        


}





int main()


{


    in >> n ;


    


    for (int i = 0; i < n ; i++)


        in >> v[i] ;


    


    for (int j = 1 ; j<=v[0] ; j++)


        calcola(j,1);


    


    


    out << max_ << endl ;


    in.close();


    out.close();


    return 0;


}

[filippos]

Non è abbastanza performante scusa?

[xCoder]

Non passa tutti i test in quanto a tempo (cioè per qualche caso impiega più di un secondo). Come lo ottimizzo? 

[filippos]

Scusa, avevo visto dal tuo profilo che avevi totalizzato 100 punti

Comunque sarebbe meglio che tu spiegassi cosa fa il codice piuttosto che mettere direttamente il listato, è più impegnativo per noi andare a leggerlo e capirlo, soprattutto perché non ci sono commenti

[VashTheStampede]

Scusa se mi sbaglio ma in teoria il tuo programma semplicemente le prova tutte: per ogni tappeto provo a saltare su tutti i tappeti raggiungibili e prendo la soluzione migliore.
Il primo miglioramento che hai fatto è di tipo Branch&Bound (if t>max) cioè se vedi che  soluzione può solo peggiorare allora ritorni.

La soluzione credo sia O(N^2) in quanto alla peggio hai a che fare con soluzioni decrescenti N+(N-1)+… E per ognuna ci impieghi tempo lineare.

Un hint che ti posso dare è che il problema ammette una soluzione Greedy!

[xCoder]

Ok, grazie