// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

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

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

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

   float resultado;

   if (aldea == 0)
      resultado = 0;
   else if (aldea == 1)
      resultado = paseoCorto[aldea - 1];
   else
      resultado = min(minimoCoste(paseoCorto, paseoLargo, aldea - 1) + paseoCorto[aldea - 1],
                      minimoCoste(paseoCorto, paseoLargo, aldea - 2) + paseoLargo[aldea - 2]);

   return resultado;

}

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

   int ultimaAldea = paseoCorto.size();

   return minimoCoste(paseoCorto, paseoLargo, ultimaAldea);

}
*/

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

/*
#define DESCONOCIDO -1

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

   if (resultado[aldea] == DESCONOCIDO)
      if (aldea == 0)
         resultado[aldea] = 0;
      else if (aldea == 1)
	 resultado[aldea] = paseoCorto[aldea - 1];
      else
	 resultado[aldea] = min(minimoCoste(paseoCorto, paseoLargo, aldea - 1, resultado) + paseoCorto[aldea - 1],
                                minimoCoste(paseoCorto, paseoLargo, aldea - 2, resultado) + paseoLargo[aldea - 2]);

   return resultado[aldea];

}

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

   int ultimaAldea = paseoCorto.size();

   vector<float> resultado(ultimaAldea + 1, DESCONOCIDO);

   return minimoCoste(paseoCorto, paseoLargo, ultimaAldea, resultado);

}


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

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

   int ultimaAldea = paseoCorto.size();

   vector<float> resultado(ultimaAldea + 1);

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

   return resultado[ultimaAldea];

}
*/

/***************************************************************************
 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 = minimoCoste(ejemploPaseoCorto, ejemploPaseoLargo);
   cout << "Minimo coste paseo: " << resultado << endl;
   if (resultado == 200)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}