Japan 2006 - Manhattan Wiring

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Japan 2006 - Manhattan Wiring

Post by hank » Sat Aug 18, 2007 1:38 pm

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.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Sat Sep 22, 2007 4:57 pm

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.

Post Reply

Return to “Algorithms”