Esta respuesta no requiere ese alto nivel de concepto dp. Más bien es fácil si divide el problema en subproblema.
En primer lugar, como tenemos que calcular el área de una submatriz que consiste en 1, es importante almacenar el valor de los 1 continuos en una matriz 2d. Definamos dp [i] [j] (i <r y j <c para índice basado en 0) como el número de uno continuo desde el índice (i, j) y hacia la izquierda desde (i, j) . ¿Cómo llenamos esta matriz?
si mat [i] [j] = 0: dp [i] [j] = 0
más dp [i] [j] = dp [i-1] [j] + 1
manejar los casos base también para i == 0
Como hemos llenado esto, el área para una submatriz con la esquina superior derecha como (i, j) se puede calcular usando dp [i] [j]. Aunque no es directo.
- ¿Cuáles son algunos algoritmos interesantes que se han encontrado en la naturaleza?
- Cómo aprender a escribir buenos algoritmos
- ¿Cómo funciona el algoritmo de búsqueda de ciclo de Floyd? ¿De qué manera mover la tortuga al comienzo de la lista vinculada, mientras se mantiene a la liebre en el lugar de reunión, seguido de mover un paso a la vez, hace que se encuentren en el punto de inicio del ciclo?
- Cómo ganar un producto CodeChef o Codeforces (pegatinas especiales)
- ¿Cómo podemos demostrar que el reconocimiento de objetos basado en la visión es un problema np completo?
Ahora para la segunda parte donde encuentre el área máxima de submatriz con 1’s. Para esto, tome una columna particular de la matriz dp y ordénela. ¿Por qué ordenarlo? Porque tenemos la libertad de reorganizar las filas en cualquier orden. Y la clasificación nos asegurará que al menos todas las columnas tenemos todos los 1 juntos en la columna y las filas con 1 continuos en orden creciente / decreciente (tratando de ser codiciosos aquí).
Para encontrar la respuesta
para (int j = 1; j <= m; j ++) {
para (int i = 1; i <= n; i ++)
ar [i] = dp [i] [j]; \
ordenar (ar + 1, ar + 1 + n);
para (int i = 1; i <= n; i ++)
ans = max (ans, ar [i] * (n-i + 1));
}
Ahora la prueba: a medida que la matriz se ordena en orden creciente, si seleccionamos una celda de la columna que dice ar [i], estamos seguros de que el área de la submatriz como la esquina superior derecha e inferior (i, j) La esquina derecha (j, n) es ar [i] * (n-i + 1). Esto se debe a que todas las celdas tienen una longitud de 1 continuo mayor que esta y, por lo tanto, el área máxima es min (ancho) * altura donde min (ancho) es ar [i] y la altura es n-i + 1.
