// 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 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];
      // Equivale a resultado = minimoCoste(paseoCorto, paseoLargo, aldea + 1) + paseoCorto[aldea];
   else
      resultado = min(minimoCoste(paseoCorto, paseoLargo, aldea + 1) + paseoCorto[aldea],
		      minimoCoste(paseoCorto, paseoLargo, aldea + 2) + paseoLargo[aldea]);

   return resultado;

}

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

   return minimoCoste(paseoCorto, paseoLargo, 0);

}
*/

/***************************************************************************
 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) {

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

   }

   return resultado[aldea];

}

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

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

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

}
*/

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

/*
float minimoCoste(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];
      else
	 resultado[aldea] = min(resultado[aldea + 1] + paseoCorto[aldea],
				resultado[aldea + 2] + paseoLargo[aldea]);

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

}