Uva Online Judge 11691 - Allergy Test

Uva Online Judge 11691 - Allergy Test

http://uva.onlinejudge.org/external/116/11691.html

Al leer este problema, inmediatamente me di cuenta que se podía resolver con programación dinámica utilizando una mascara de bits, esta mascara de bits representaría las pruebas que ya eh utilizado, adicional a eso necesitaría llevar en mi programación dinámica, el espacio en días que la prueba anterior ocupa de tal manera que yo puedo hacer una prueba en cualquiera de esos días sin que impida saber si hay una reacción en la prueba anterior.

Al implementarlo fue un rotundo tiempo de ejecución excedido, paso bastante tiempo en que volviera a tratar de resolver el problema, después de meditar un rato, no era necesario saber si una prueba ya fue utilizada, si no podría diferenciarla por tamaño de días que dura su reacción y no individualmente, esto me dejaría que el numero de estados posibles no eran de 2^20 si no de las combinaciones de 20 en 7 que es muchísimo menor, para implementar la solución utilicé un map de c++ para llevar la información.

/*
Autor: Rodrigo Burgos Dominguez
Problem: 11691 - Allergy Test
Algoritm: Programacion Dinamica
*/

# include "stdio.h"
# include "string.h"
# include "algorithm"
# include "map"

using namespace std;

typedef struct { int values[8]; } DATA;

bool operator < ( DATA A, DATA B ){
  int x;
  for( x = 0; x < 8; x++) if( A.values[x] != B.values[x]) return A.values[x] < B.values[x];
  return 0; 
}

map< DATA, int > din[8];
map< DATA, int > vis[8];

int solve( int sizePrevius, DATA currentState){
  int res = (1<<30), x, cnt = 0, y;
  DATA next;
  if( vis[ sizePrevius][currentState] == 1)
     return din[sizePrevius][currentState];  
  vis[ sizePrevius][currentState] = 1;
  for( x = 0; x < 8; x++) if( currentState.values[x] > 0 ){
   cnt++;
   for( y = 0; y <= sizePrevius; y++) if( x - y > 0){
     next = currentState;
     next.values[x]--,
     res = min( res, solve( (x - y) - 1 , next) + sizePrevius + 1);
   }
  }
  if(cnt == 0 ) res = sizePrevius;
  return din[sizePrevius][currentState] = res;
}

main(){
  int ncases, cases, x, n, val;
  DATA empty;
  memset( empty.values, 0, sizeof( empty.values ));
  for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++){
     for( x = 0; x < 7; x++){
      map< DATA, int > visEmpty;
      vis[x] = visEmpty;
     }
     scanf("%d", &n);
     DATA ini = empty;
     for( x = 0; x < n; x++){
      scanf("%d", &val);
      ini.values[ val ]++;
     }
     printf("%d\n", solve( 0 , ini ));
  }
  return 0; 
}

Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com