Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
836 – Largest Submatrix

El problema es de Programación Dinámica.
Lo que nos piden es encontrar el rectángulo de números ‘1’ mas grande en la matriz.
Esto se reduce a un Max Sum.
La idea es utilizar programación dinámica para generar todos los posibles rectángulos y de lo obtenido, decir el tamaño del rectángulo mas grande.

Los únicos detalle son:

  • Los números ‘0’ de la matriz, hay que pasarlos a un numero negativo lo suficiente mente grande. Un valor de -1000 es suficiente
  • Hay que dejar un enter entre cada caso de prueba.

El algoritmo de Max Sum que calcula todos los rectángulos es de complejidad O(n^4) que da Accepted en el problema.
Igual existe la solución de Max Sum en un tiempo de complejidad O(n^3).

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: