Page 1 of 1

Japan 2006 - Manhattan Wiring

Posted: Sat Aug 18, 2007 1:38 pm
by hank
Japan 2006 - Manhattan Wiring

This problem is from ACM ICPC Japan regional 2006.

Some people solved this problem by DP.
But I don't know how to apply DP on this problem.
Does anybody know how to solve this problem by DP?
Thanks in advance.

Posted: Sat Sep 22, 2007 4:57 pm
by Ivan
This problem is very similar to problem "connect" from CEOI 2006:

And you may also look at the solution at:

Altough the ACM one is a bit easier.