Algoritmos y Demas

Hoy entre de nuevo a Topcoder, el SRM 565 con un poco de emoción y recelo debido a que no eh entrado a un concursos tipo Topcoder desde ya hace 11 meses, y como era de esperarse me fue muy mal, sacando 0 puntos.
En los próximos meses pretendo entrenar a alumnos para los Regionales de ACM y debo ponerme a practicar aun que sea en CodeForces y Topcoder, también debo hacer la misma tarea que ellos hacen, cada problema que no podamos resolverlo en el concurso tratarlo de sacar de tarea y aquí voy a explicar algunos de ellos como se resuelven.

Empecemos, este el problema:

Resumiendo el problema: tienes que crear un método llamado minimumPrice que reciba dos arreglos long[] dread y int[] Price , tu tienes que pasar por una serie de mostro en el orden establecido , cada mostro es sobornable y por lo tanto puedes pagar un precio ( que va de 1 a 2 ) , si lo pagas el mostro te apoyara con los siguientes mostros, si no lo pagas el te atacar si y solo si su temor ( que es igual a su valentía ) es mayor que la suma de todos los mostros que se hallan comprado.

Tu tarea es calcular el mínimo precio para pasar por todos los mostros sin ser atacado.

Con esta información se puede plantear una dinámica muy sencilla de posición x temor , el numero de mostros es menor a 50 , pero el temor esta entre 1 y 10^12, lo cual arruina completamente esta dinámica simple.

Pase varios minutos sin encontrar una manera de resolver el problema de manera optima con una programación dinámica, por lo tanto hice un glotón que sospechaba fuertemente no era suficiente para resolver todos los casos de prueba y así fue.

Revisando soluciones de otros programadores y viendo como lo resolvieron, la programación dinámica era correcta, solo que en vez de tomar la posición y la bravura, era la posición y el precio guardando la suma de todos los miedos ( me recordó a una película no se por que) o mejor dicho maximizando la suma de todos los mostros sobornados con un costo especifico, y de ahí basarnos para calcular si el siguiente mostro se puede sobornar o se puede pasar derecho con cierta cantidad de dinero, si no se puediera se marcaria con -1 o con algún valor para determinar con ese costo no se pudo superar ese mostro.

Veamos el código:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class MonstersValley {
public:
	int minimumPrice(vector <long long>, vector <int>);
};

long long din[51][101];

int MonstersValley::minimumPrice(vector<long long> dread, vector <int> price) {
	memset(din, -1, sizeof( din )); // marcamos como imposible todas las posiciones
	din[0][price[0]] = dread[ 0 ]; // la unica manera de pasar al primero mostro es sobornandolo
	for( int currentMonster = 1; currentMonster < dread.size() ; currentMonster++ ){
	    for( int cost = 0; cost <= dread.size() * 2  ; cost++)
	      if(din[currentMonster - 1][ cost] >= 0 ){
	          if( din[currentMonster -1][ cost] >= dread[ currentMonster ] )
	               din[currentMonster][cost ]  = max(din[currentMonster][cost ] , din[currentMonster-1][cost ] );
	          din[currentMonster][cost +price[currentMonster]]  =
	                 max(din[currentMonster][cost + price[currentMonster]] , 
	                     din[currentMonster-1][cost ]  + dread[currentMonster]);
	      }
	}
	for(int cost = 0; cost <= dread.size() * 2 ; cost++ ){
	    if(din[dread.size() - 1 ][ cost ] >= 0 ) return cost;
	}
	return -1;
}


//Powered by [KawigiEdit] 2.0!