3986 - The Bridges of Kölsberg

Enunciado

Programación dinámica, dynamic programming, DP.

dp[i][j] = Máximo puntaje que puedo alcanzar habiendo creado puentes válidos entre las primeras i ciudades del norte y las primeras j ciudades del sur.

b[i][j] = Mínima cantidad de puentes que necesito para obtener un puntaje de dp[i][j].

Notar que dp[i][j] es el máximo entre tres posibles opciones:

• dp[i-1][j-1] + valor_norte[i] + valor_sur[j], siempre y cuando la ciudad norte-i y la ciudad sur-j tengan el mismo sistema operativo. Representa la opción de conectar los dos puentes.
  
• dp[i][j-1]. Representa la opción de lograr un mejor puntaje ignorando la ciudad actual del sur.
  
• dp[i-1][j]. Representa la opción de lograr un mejor puntaje ignorando la ciudad actual del norte.

Complejidad: O(n²)
Código fuente