// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

void mostrarViaje(const vector<float> & paseoCorto,
		  const vector<float> & resultado) {

   int ultimaAldea = paseoCorto.size();

   int aldea = 0;

   cout << "Viaje mas barato:";
   while (2 + 2 == 4) {
      cout << " " << aldea;
      if (aldea == ultimaAldea) {
	 cout << endl;
	 return;
      } else if (aldea == ultimaAldea - 1)
	 aldea = aldea + 1;
      else if (resultado[aldea] == paseoCorto[aldea] + resultado[aldea + 1])
	 aldea = aldea + 1;
      else
	 aldea = aldea + 2;
   }   


   
}

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
float minimoCostePaseo(const vector<float> & paseoCorto,
		       const vector<float> & paseoLargo,
		       int aldea) {

   // Minimo coste de llegar desde esa aldea hasta la ultima aldea

   float resultado;

   int ultimaAldea = paseoCorto.size();

   if (aldea == ultimaAldea)
      resultado = 0;
   else if (aldea == ultimaAldea - 1)
      resultado = paseoCorto[aldea];
      // Tambien resultado = minimoCostePaseo(paseoCorto, paseoLargo, aldea + 1) + paseoCorto[aldea];
   else
      resultado = min(minimoCostePaseo(paseoCorto, paseoLargo, aldea + 1) + paseoCorto[aldea],
		      minimoCostePaseo(paseoCorto, paseoLargo, aldea + 2) + paseoLargo[aldea]);

   return resultado;

}

float minimoCostePaseo(const vector<float> & paseoCorto,
		       const vector<float> & paseoLargo) {

   return minimoCostePaseo(paseoCorto, paseoLargo, 0);

}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

float minimoCostePaseo(const vector<float> & paseoCorto,
		       const vector<float> & paseoLargo,
		       int aldea,
		       vector<float> & resultado) {


   if (resultado[aldea] == DESCONOCIDO) {

      int ultimaAldea = paseoCorto.size();
      
      if (aldea == ultimaAldea)
	 resultado[aldea] = 0;
      else if (aldea == ultimaAldea - 1)
	 resultado[aldea] = paseoCorto[aldea];
      else
	 resultado[aldea] = min(minimoCostePaseo(paseoCorto, paseoLargo, aldea + 1, resultado) + paseoCorto[aldea],
				minimoCostePaseo(paseoCorto, paseoLargo, aldea + 2, resultado) + paseoLargo[aldea]);

   }

   return resultado[aldea];

}

float minimoCostePaseo(const vector<float> & paseoCorto,
		       const vector<float> & paseoLargo) {

   vector<float> resultado(paseoCorto.size() + 1, DESCONOCIDO);

   float mc = minimoCostePaseo(paseoCorto, paseoLargo, 0, resultado);
   mostrarViaje(paseoCorto, resultado);
   return mc;

}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
float minimoCostePaseo(const vector<float> & paseoCorto,
	               const vector<float> & paseoLargo) {

   vector<float> resultado(paseoCorto.size() + 1);

   int ultimaAldea = paseoCorto.size();


   for (int aldea = ultimaAldea; aldea >= 0; aldea--)
      if (aldea == ultimaAldea)
	 resultado[aldea] = 0;
      else if (aldea == ultimaAldea - 1)
	 resultado[aldea] = paseoCorto[aldea];
         // Tambien resultado[aldea] = resultado[aldea + 1] + paseoCorto[aldea];
      else
	 resultado[aldea] = min(resultado[aldea + 1] + paseoCorto[aldea],
				resultado[aldea + 2] + paseoLargo[aldea]);

   mostrarViaje(paseoCorto, resultado);

   return resultado[0];

}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main() {

   // Este ejemplo corresponde a un rio con n = 7 aldeas numeradas de 0 a 6
   // El paseo corto esta disponible en las aldeas 0 a 5
   // El paseo largo esta disponible en las aldeas 0 a 4

   vector<float> ejemploPaseoCorto = {80, 20,  60,  50, 90, 10};
   vector<float> ejemploPaseoLargo = {70, 30, 100, 110, 40};

   float resultado = minimoCostePaseo(ejemploPaseoCorto, ejemploPaseoLargo);
   cout << "Minimo coste paseo: " << resultado << endl;
   if (resultado == 200)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}