Problema de Backtracking (recursion)

Iniciado por KINGARZA, 6 Julio 2017, 08:17 AM

0 Miembros y 1 Visitante están viendo este tema.

KINGARZA

Hola que tal, ando intentando un problema de un juez en linea https://omegaup.com/arena/problem/decepcion#problems

Dado un entero n, se forma una fila de n torres con alturas desde 1 hasta n centímetros, ninguna altura aparece más de una vez. Se quieren conocer todas las permutaciones de esta fila tal que viendo la fila de frente solo se vean F torres diferentes y vista por detrás solo se vean B torres. Se dice que podemos ver una torre con altura H si no hay otra torre delante de ella (con respecto a nuestra visión) con altura mayor a H.

Entrada

Tres enteros separados por espacios: n, F y B.

Salida

Un entero que representa el número de permutaciones que cumplen con las condiciones establecidas.

Ejemplo

4 2 3
3
Las tres permutaciones posibles son:
Frente → 2 4 3 1
Frente → 1 4 3 2
Frente → 3 4 2 1

Límites

1≤n,F,B≤13


En el cual tengo una respuesta que me da 55 puntos, me da tiempo limite excedido
Podrias darme una ayuda?
Por ejemplo alguna poda o mucho mejor alguna pagina donde expliquen temas de este tipo
, etc..., todo es bueno.
Bueno y pues lo que hago es literal hacer lo que pide el problema, no tengo ninguna poda
(en un principio pense que el numero mayor seria un numero fijo, si viste en el ejemplo viene:

4 2 3
3
Las tres permutaciones posibles son:
Frente → 2 4 3 1
Frente → 1 4 3 2
Frente → 3 4 2 1

pero si pongo este otro caso ya no es factible

5 3 2

unas permutaciones posibles son:

12534

13254

)
Código (cpp) [Seleccionar]

#include <bits/stdc++.h>
using namespace std;

bool visitado[15];
string cad[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", ":",";", "<", "="};//si checas el codigo ascii despues del 9 sigue el ":" y luego el ";", etc..., es decir, que poner ":" es como poner 10, etc.

int n, x, y, C;//C = contador = permutaciones validas

bool esValido_izq(string tmp){
   int a = 1, mayor = tmp[0];
   for(int i = 1; i < n; i++)
       if(tmp[i] > mayor)
           mayor = tmp[i], a++;
   return (a == x);
}

bool esValido_der(string tmp){
   reverse(tmp.begin(), tmp.end());
   int a = 1, mayor = tmp[0];
   for(int i = 1; i < n; i++)
       if(tmp[i] > mayor)
           mayor = tmp[i], a++;
   return (a == y);
}

void permutar(string tmp = ""){
if(tmp.size() == n){
       if(esValido_izq(tmp) && esValido_der(tmp)){
           C++;
           //cout<<"\n"<<tmp<<"\n"; //descomentar para ver las permutaciones validas
       }
       return;
}
for(int i = 0; i < n; i++)
if(!visitado[i]){
visitado[i] = true;
permutar(tmp + cad[i]);
visitado[i] = false;
}
}

int main(){
   cin>>n>>x>>y;
   permutar();
   cout<<C;
}