=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Examen final - 2023/2024
23 de enero de 2024
Ejercicio 10
Borrador
=================================================================


Las siguientes soluciones tienen los siguientes costes:

Coste temporal: O(n * k^2)
Coste espacial: O(n * k + k^2)


Solucion 1
==========

a) VERSION EFICIENTE RECURSIVA

#define DESCONOCIDO -1

float maxPuntos(int contrincante,
		int combate,
		const vector<float> & puntosVencer,
		const vector<vector<float> > & puntosEvolucion,
		vector<vector<float> > & resultado) {
   
   // Maxima cantidad de puntos que el jugador puede acumular desde el combate 0 hasta ese combate
   // si en ese combate supera a ese contrincante

   if (resultado[contrincante][combate] == DESCONOCIDO)
      if (combate == 0)
	 resultado[contrincante][combate] = puntosVencer[contrincante];
      else {
	 int contrincantes = puntosVencer.size();
	 float maximo = 0;
	 for (int contrincantePrevio = 0; contrincantePrevio < contrincantes; contrincantePrevio++)
	    maximo = max(maximo,
			 maxPuntos(contrincantePrevio, combate - 1, puntosVencer, puntosEvolucion, resultado)
			 + puntosEvolucion[contrincantePrevio][contrincante] + puntosVencer[contrincante]);
	 resultado[contrincante][combate] = maximo;
      }

   return resultado[contrincante][combate];

}

float maxPuntos(int combates,
		const vector<float> & puntosVencer,
		const vector<vector<float> > & puntosEvolucion) {

   int contrincantes = puntosVencer.size();
   vector<vector<float> > resultado(contrincantes, vector<float>(combates, DESCONOCIDO));
   int ultimoCombate = combates - 1;
   float maximo = 0;
   for (int contrincanteFinal = 0; contrincanteFinal < contrincantes; contrincanteFinal++)
      maximo = max(maximo,
		   maxPuntos(contrincanteFinal, ultimoCombate, puntosVencer, puntosEvolucion, resultado));

   return maximo;

}


b) VERSION EFICIENTE NO RECURSIVA

float maxPuntos(int combates,
		const vector<float> & puntosVencer,
                const vector<vector<float> > & puntosEvolucion) {

   int contrincantes = puntosVencer.size();
   vector<vector<float> > resultado(contrincantes, vector<float>(combates));
   float maximo;
   
   for (int combate = 0; combate < combates; combate++)
      for (int contrincante = 0; contrincante < contrincantes; contrincante++)
	 if (combate == 0)
	    resultado[contrincante][combate] = puntosVencer[contrincante];
	 else {
	    maximo = 0;
	    for (int contrincantePrevio = 0; contrincantePrevio < contrincantes; contrincantePrevio++)
	       maximo = max(maximo,
			    resultado[contrincantePrevio][combate - 1]
			    + puntosEvolucion[contrincantePrevio][contrincante] + puntosVencer[contrincante]);
	    resultado[contrincante][combate] = maximo;
	 }

   int ultimoCombate = combates - 1;
   maximo = 0;
   for (int contrincanteFinal = 0; contrincanteFinal < contrincantes; contrincanteFinal++)
      maximo = max(maximo,
		   resultado[contrincanteFinal][ultimoCombate]);

   return maximo;

}


Solucion 2
==========

a) VERSION EFICIENTE RECURSIVA

#define DESCONOCIDO -1

float maxPuntos(int contrincantePrevio,
		int combate,
		int combates,
		const vector<float> & puntosVencer,
		const vector<vector<float> > & puntosEvolucion,
		vector<vector<float> > & resultado) {

   // Maxima cantidad de puntos que el jugador puede acumular desde ese combate hasta el ultimo
   // si en el combate previo supero a contrincantePrevio

   if (resultado[contrincantePrevio][combate] == DESCONOCIDO)
      if (combate == combates)
	 resultado[contrincantePrevio][combate] = 0;
      else {
	 int contrincantes = puntosVencer.size();
	 float maximo = 0;
	 for (int contrincante = 0; contrincante < contrincantes; contrincante++)
	    maximo = max(maximo,
			 puntosEvolucion[contrincantePrevio][contrincante] + puntosVencer[contrincante]
			 + maxPuntos(contrincante, combate + 1, combates, puntosVencer, puntosEvolucion, resultado));
	 resultado[contrincantePrevio][combate] = maximo;
      }

   return resultado[contrincantePrevio][combate];

}

float maxPuntos(int combates,
		const vector<float> & puntosVencer,
		const vector<vector<float> > & puntosEvolucion) {

   int contrincantes = puntosVencer.size();
   vector<vector<float> > resultado(contrincantes, vector<float>(combates + 1, DESCONOCIDO));
   float maximo = 0;
   for (int contrincantePrimero = 0; contrincantePrimero < contrincantes; contrincantePrimero++)
      maximo = max(maximo,
		   puntosVencer[contrincantePrimero] + maxPuntos(contrincantePrimero, 1, combates, puntosVencer, puntosEvolucion, resultado));
 
return maximo;

}


b) VERSION EFICIENTE NO RECURSIVA

float maxPuntos(int combates,
		const vector<float> & puntosVencer,
		const vector<vector<float> > & puntosEvolucion) {

   int contrincantes = puntosVencer.size();
   vector<vector<float> > resultado(contrincantes, vector<float>(combates + 1));

   for (int combate = combates; combate >= 0; combate--)
      for (int contrincantePrevio = 0; contrincantePrevio < contrincantes; contrincantePrevio++)
	 if (combate == combates)
	    resultado[contrincantePrevio][combate] = 0;
	 else {
	    float maximo = 0;
	    for (int contrincante = 0; contrincante < contrincantes; contrincante++)
	       maximo = max(maximo,
			    puntosEvolucion[contrincantePrevio][contrincante] + puntosVencer[contrincante]
			    + resultado[contrincante][combate + 1]);
	    resultado[contrincantePrevio][combate] = maximo;
	 }
   
   
   float maximo = 0;
   for (int contrincantePrimero = 0; contrincantePrimero < contrincantes; contrincantePrimero++)
      maximo = max(maximo,
		   puntosVencer[contrincantePrimero] + resultado[contrincantePrimero][1]);
   
   return maximo;
   
}