Page 1 of 1

Japan 2006 - Manhattan Wiring

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

http://acm.pku.edu.cn/JudgeOnline/problem?id=3133

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:

http://www.hsin.hr/ceoi2006/tasks/day2/connect.pdf

And you may also look at the solution at:

http://www.hsin.hr/ceoi2006/tasks/solutions.pdf

Altough the ACM one is a bit easier.