Cómo resolver ADAGAME en SPOJ

Sea n el número actual y el turno actual sea t:

MinMax(n,t)={

[matemáticas] [/ matemáticas] ans=0;

for each of four combinations N of n :

if turn is odd ie, Ada's turn :

ans=max(ans,MinMax(N,t+1)) //Ada tries to maximize

else if turn is even ie, Vinit's turn :

ans=min(ans,MinMax(N,t+1)) //Vinit tries to minimize

return ans;

}

El código anterior devuelve el número más óptimo

Si el número final obtenido arriba es mayor que el número original, Ada gana más, Vinit gana

¡Pero tienes que memorizarlo o obtendrás TLE!

Recordarlo usando dp. Inicialice dp de la siguiente manera:

dp[n][t]=-1 for n = 1 to 10000 and t= total number of turns allowed

Entonces, después de podar su pseudocódigo ahora se convierte en:

MinMax (n, t) = {
ans = 0;
if (t> max_no_of_turns) devuelve n; //caso base
if (dp [n] [t]> = 0) devuelve dp [n] [t];
para cada una de las cuatro combinaciones N de n:
si el turno es impar, es decir, el turno de Ada:
ans = max (ans, MinMax (N, t + 1)) // Ada intenta maximizar
si el turno es par, es decir, el turno de Vinit:
ans = min (ans, MinMax (N, t + 1)) // Vinit intenta minimizar
devuelve dp [n] [t] = ans;
}

Espero que responda tu pregunta. ¡Feliz codificación!

El problema de ADFRUITS se puede resolver utilizando LCS (subsecuencia común más larga), si no conoce LCS, puede consultar estos enlaces:

• Programación Dinámica | Set 4 (Subsecuencia común más larga) – GeeksforGeeks

Entonces, en este problema, primero estamos calculando el LCS de dos cadenas que nos han dado y luego, usando el rastreo, encontramos los índices en ambas cadenas que contribuyen al LCS. almacenaremos estos valores en una matriz temporal bool.

Tomemos un ejemplo de manzana y pera, sabemos que en la aplicación son comunes las peras.

entonces para apple ==> falso falso verdadero falso verdadero

y para pera ==> verdadero verdadero falso falso

Luego, construiremos nuestra cadena de resultados al considerar primero todos los alfabetos hasta que seamos verdaderos.

lo mismo que hacemos para nuestra segunda cadena, luego incluya los alfabetos que forman parte de LCS y repita estos pasos hasta llegar al final de ambas cadenas.

para el código, consulte esto: Frutas avanzadas – ADFRUITS