Cómo resolver el problema de ‘La lista negra’ en un CodeSprint reciente de HackerRank

¿Mi respuesta llega demasiado tarde? Solo resuelve el problema …
Utilizo una recurrencia de diferencia para resolver el problema con DP.

Problema redeclarar:
Supongamos que hay n gangster y k killers que contratamos, ¡queremos que los k killers maten a todos n gangster con un costo mínimo! Antes de DP, definamos el subproblema en primer lugar.

Definir:
[matemáticas] dp [i] [j] [m] [/ matemáticas]
como el subproblema:
El costo mínimo para matar al primer gángster [1 … j] del gángster [1 … n] (j <= n), y el gángster [j] es asesinado por el asesino [i], y m describe al asesino al que contratamos matar al gángster [1 … j]
La oración resaltada describe el subproblema, que es un poco complicado. Hay 3 información clave en la definición de subproblema, y ​​están separados por “y” (y no se resalta más arriba).

¡Así que analicémoslos uno por uno!

1. El dp [i] [j] [m] es el costo mínimo para matar a la primera parte del gángster [1 … j] , esto es muy común para una solución DP, porque descompone al gángster n y lo reduce a un tamaño más pequeño de problema. Sin embargo, desglosar el tamaño del gángster solo no es suficiente. Por lo tanto, necesitamos la restricción 2 y 3
2. El gángster [j] es asesinado por el asesino [i]. Esto es muy importante, tenemos que decir explícitamente el subproblema: qué asesino mata al gángster j por cada j. Porque el problema dice: cada asesino debe matar consecutivamente. Si perdemos la información de la identificación del asesino, no hay formas de DP
3. m describe al asesino que contratamos para matar al gángster [1 … j], este es el mismo uso de la restricción 2. En realidad, B está comprendido entre [0, 2 ^ k], es una máscara para describir qué asesinos tienen usado para derribar al gángster [1 … j]. Si no tiene esta información, no sabemos si podemos usar un asesino para matar al gángster j + 1. EG: m = (000101) b, en este caso, usamos el primer y tercer asesino para derribar al primer gángster j, por lo tanto, cuando calculamos dp [x] [j + 1] [y] sabemos qué hacer .

Después de la definición del subproblema, echemos un vistazo a la recurrencia.
[matemáticas] dp [i] [j] [m] = costo [i] [j] + min {dp [x] [j-1] [m & ~ (1 << i)], dp [i] [ j-1] [m]]}, donde x! = i y 0 <= x

Analicemos la recurrencia ahora, la recurrencia consta de 2 partes

1. si el gángster [j-1] es asesinado por un asesino de diferencias, que se describe en la primera parte. Recorre cada asesino excepto el i-ésimo para encontrar el costo mínimo. La dimensión de máscara de bits es (m & ~ (1 << i)), lo que significa que el asesino i-ésimo no se selecciona al matar al gángster [1 ... j-1].
2. si el gángster [j-1] es asesinado por el mismo asesino que el gángster [j], que se describe en la segunda parte. Solo necesitamos mirar un estado: dp [i] [j-1] [m]. La clave es mantener m la misma, porque el asesino está haciendo un asesinato consecutivo, por lo que la máscara de bits para indicar que la información del asesino permanece igual. (No estamos usando un nuevo asesino, ¿verdad?). Y simplemente configuramos j -> j-1 para recuperar la información anterior.

Lo último que debe prestar atención es lo que podemos tomar. ¿Podemos tomar m de 0 – 2 ^ k? Entonces la respuesta es NO! Algunos m no tienen sentido. Por ejemplo, si estamos discutiendo j = 2, y la m = (110111) b no es válida porque describe CINCO asesinos son contratados por nosotros solo estamos en j = 2. Entonces, verifique el número de 1s para m antes de la recurrencia. La complejidad del tiempo es O (k * n * 2 ^ k * k) = O (max (2 ^ k, nk ^ 2)). Si k es demasiado grande, no podemos resolver el problema incluso con DP …