Preguntas del examen olímpico provincial de informática de Anhui (grupo de escuela primaria) 2013 Respuesta a la tercera pregunta

Usamos map[i][j] para registrar el número de caramelos en cada celda. Para las células que han sido mordidas por ratones, cambiamos la cantidad de caramelos en esta celda a un número negativo pequeño (por ejemplo, -10000000), de modo que el problema sea encontrar una suma y la submatriz más grande.

Preprocese la matriz f[i][j] para representar map[1][j] map[2][j] map[3][j] ...map[i][j] .

Después de preprocesar la matriz F, podemos encontrar fácilmente la suma de todos los dulces en la columna K desde la fila I hasta la fila J.

(es decir, f[j][k]-f[i-1][k])

De esta manera, podemos enumerar el límite superior I y el límite inferior J , utilizando el límite I y el límite inferior J, encuentre la submatriz más grande para actualizar la respuesta.

Defina la matriz b[k]=f[j][k]-f[i-1][k]

El problema pasa a ser encontrar un intervalo l~r tal que b[ l] b[l 1] ...b[r] valor máximo.

Redefinir c[i]=b[1] b[2] ...b[i]

Entonces la suma de l~r se puede expresar como c[r] -c[l-1].

Entonces, para cada límite superior e inferior determinado, enumeramos el C más pequeño entre los registros R 1~r-1 y lo restamos de c[r] para actualizar la respuesta.

Puedes intentar escribir el código tú mismo. Si realmente lo necesitas, puedes preguntarme.