Aquí hay una solución de programación dinámica simple.
Sea ar [i] el valor de la i-ésima moneda desde abajo. Define DP (i, j) = mejor suma que el próximo jugador puede sacar de las monedas i inferiores si se les permite tomar hasta j monedas en su próximo movimiento. Obviamente, DP (N, 2) es lo que nos han pedido que encontremos. También defina sum (i) = la suma de las monedas i inferiores.
Ahora, si j = 1, el siguiente jugador tiene que tomar exactamente una moneda. Luego, el jugador contrario se queda con monedas i-1 de las cuales puede hacer una suma de DP (i-1,2) en el mejor de los casos. Por lo tanto, la mejor suma total para el jugador actual es ar [i] + sum (i-1) -DP (i-1,2) = sum (i) -DP (i-1,2).
- Cómo abordar el problema 'Mapa intergaláctico' (IM) en SPOJ usando Max Flow
- Dada una expresión matemática 2 + 4 * 6 + 8-11, ¿cómo la colocaría entre corchetes de manera que proporcione el valor máximo? ¿Es posible codificar esto?
- ¿De dónde obtienen los algoritmos comerciales sus datos sin procesar?
- ¿Cuáles son algunos algoritmos que usamos diariamente que tienen complejidades [matemáticas] O (n), O (n ^ 2), [/ matemáticas] y [matemáticas] O (\ log n) [/ matemáticas]?
- Tengo un examen de matemáticas discreto y esto está en él. ¿Cuál es la fórmula recursiva de an = an-1 + 2?
De lo contrario, el siguiente jugador tiene que tomar j monedas en el próximo movimiento o un número menor de j. En el primer caso, la mejor suma total para el jugador actual es sum (i) -sum (ij) + sum (ij) -DP (ij, 2j) = sum (i) -DP (ij, 2j). En el segundo caso, la mejor suma es solo DP (i, j-1).
Combinando estos y observando las condiciones de contorno, obtenemos las relaciones de recurrencia y los casos base:
DP (0, j) = 0
DP (i> 0,1) = suma (i) -DP (i-1,2)
DP (i> 0,1 <j <= i) = max (DP (i, j-1), sum (i) -DP (ij, 2j))
DP (i> 0, j> i) = DP (i, i)
Con estos, DP (N, 2) se puede evaluar en O (N ^ 2)
