¿Cómo resolver el problema de corchetes en SPOJ (SPOJ: SQRBR)?

Solución pobre: ​​Considere 4-d DP donde [math] (i, j, k, l) [/ math] denota la expresión de la longitud [math] i [/ math], con [math] j [/ math] corchetes abiertos, [matemática] k [/ matemática] corchetes cerrados, [matemática] l = 0 o 1 [/ matemática] que indica el estado del último paréntesis, es decir, abierto o cerrado. Deje abrir = 1, cerrar = 0.

1. Tenemos [matemáticas] (i, j, k, 0) = (i-1, j, k-1,0) + (i-1, j, k-1,1) [/ matemáticas]
2. También [matemáticas] (i, j, k, 1) = (i-1, j-1, k, 0) + (i-1, j-1, k, 1) [/ matemáticas]
3. Condiciones imponentes: [matemática] (i, j, k, 0) = 0 [/ matemática] si se requiere la posición i-ésima para permanecer abierta.
4. [matemáticas] (0, j, k, l = 0 o 1) = 1 [/ matemáticas] si [matemáticas] j = k = 0 [/ matemáticas]
5. [matemáticas] (i, j, k, l) = 0 [/ matemáticas] si [matemáticas] k> j [/ matemáticas] (¿Por qué?)
6. La respuesta requerida es [matemáticas] (2n, n, n, 0) / 2 [/ matemáticas] (¿Por qué dividir por 2?)

Aquí hay una implementación idéntica a la respuesta de Raziman Thottungal Valapu

  #include 
 #include 
 #include 
 #include 

 #define REP (i, n) para (int i = 0; i > d;
     mientras que (d -) {
         int n;  cin >> n;
         int k;  cin >> k;
         memset (dp, 0, sizeof (dp));
         establecer  s;
         REP (i, k) {
             int x;  cin >> x;  s.insert (x);
         }    
         para (int i = 1; i <= 2 * n; i ++) {
             para (int j = 0; j <= i; j ++) {
                 si (i == 1) {
                     si (j == 1) dp [i] [j] = 1;
                     de lo contrario dp [i] [j] = 0;
                 }más{
                     if (s.find (i)! = s.end ()) {
                         dp [i] [j] = ((j == 0)? 0: dp [i-1] [j-1]);
                     }más{
                         dp [i] [j] = dp [i-1] [j + 1] + ((j == 0)? 0: dp [i-1] [j-1]);
                     }
                 }
             }
         }
         cout << dp [2 * n] [0] << endl;
     }
 } 

Daría un algoritmo DP algo diferente.

Necesita tener N “]” llaves de cierre. La idea ahora es determinar en qué lugares puede insertar esto.
Tendremos una matriz N * 2N. (Aquí el índice de fila, i, (max N) indica el recuento para el caso de i número de llaves “]”).
Su resultado [i] [j] indica el recuento de todos los casos en los que puede hacer que i cierre las llaves hasta la posición de secuencia j.
Esto se puede calcular mediante la relación de recurrencia:
si j es igual a la posición “[” especificada, resultado [i] [j] = resultado [i] [j-1],
de lo contrario, resultado [i] [j] = resultado [i] [j-1] + resultado [i-1] [j-1]

Además, para cada fila, las entradas hasta j = 2 * i, solo serán 0. (Como, es imposible insertar la i-ésima llave de cierre para cada posición antes de eso).
Finalmente, el caso base, para llenar la primera fila (cuando está llenando una sola llave “]”, aplique esta relación):
si j es igual a la posición “[” especificada, resultado [0] [j] = resultado [0] [j-1],
de lo contrario, resultado [0] [j] = resultado [0] [j-1] + 1

El resultado final es => resultado [n-1] [2 * n-1]
El tiempo de ejecución es O (n ^ 2).
Espero que esto ayude.

Recuerdo que lo resolví hace mucho tiempo, cuando recién comenzaba con DP. No era bueno para identificar estados o las recurrencias. Entonces, esto es lo que hice: supongo que funcionó el estado posible, y escribí la tabla DP. Mi suposición resultó ser correcta, y pude encontrar la relación de recurrencia analizando la tabla. ¡Y eso es!

por ejemplo: si la tabla DP se ve así

1 2 3 4 5

0 3 8 15 24

0 0 11 34 73

Entonces la relación de recurrencia es

f [i] [j] = f [i-1] [j-1] + f [i-1] [j] + f [i] [j-1] para j> = i

Sí, fue como hacer trampa, y no estoy orgulloso de ello, pero era nuevo en DP y lo resolví por mi cuenta, incluso si mi método era incorrecto. Recuerdo haber resuelto un problema de DP más en SPOJ de esta manera.

Vi que Raziman TV respondió la pregunta, y alguien también escribió el código, por lo que realmente no necesitaba escribir una respuesta real. Honestamente obtuve AC con este truco, y pensé en compartir esta historia. En caso de que te lo preguntes, no he usado este truco en más de un año, aunque no hay promesas 😉