The Bridges of Kolsberg (UVa Live Archive Europe - Southwestern - 2007/2008 Lisbon (Portugal))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3986

問題

川があってその間に橋を交差しないように架けたい。橋を架ける候補の川の両岸には都市がそれぞれN1,N2個存在し、各都市には得点と都市のタイプがある。同じタイプの都市同士にしか橋を架けれないという条件の下で、橋をたくさん架けた時の得点の和の最大値と架けた橋の数はいくらか。
片方の岸の都市の数<=1000

解法

DPで解く。
dp[i][j]は上の岸の都市でi番目の都市まで橋をかけて、下の岸のj番目の都市に橋を架けれる状態の最大得点を表す。こうしておくと、dp[i][j] = max(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + 都市の得点)となりO(1)でdpの要素の更新ができる。(最後のやつは都市のタイプが同じ場合のみ)