Asta e cea mai eficienta metoda la care am ajuns:
int f_mat[0xFFF][0xFFF];/* matricea f */
int f(int i, int j){
return f_mat[i][j];
}
int cost_min[0xFFF]; /* Reprezinta costul minim de la i la n*/
int mincost(int i){
return cost_min[i];
}
int n;
int min(int a, int b) {return a < b ? a : b;}
void gencost(){
/* initializarea cu matricea f */
for(int i = 1; i < n; i++)
cost_min[i] = f(i,n);
for(int i = n-2; i >= 1; i--){
/* vedem care e cel mai ieftin mod de a inchiria canoele de la i la n, stiind care sunt cele mai ieftine metode de a le inchiria de la j la n, oricare ar fi j din (i, n) */
for(int j = n-1; j > i; j--){
/* incercam sa impartim drumul de la i la n in doua parti: de la i la j si de la j la n, si vedem daca costul se micsoreaza daca este impartit */
cost_min[i] = min(f(i,j) + mincost(j), mincost(i));
}
}
/* complexitatea este O( n-1 + (n-2)*(n-1)/2 ) = O( (n-1)*((n-2)/2 + 1) ) = O( (n-1)*(n/2) ) = O( n(n-1)/2 ) = O( n^2 ) */
}
