解题报告：Clans on the Three Gorges
题目来源：http://acm.pku.edu.cn No.1682
解法或类型： 动态规划
作者：杭杰
Clans on the Three Gorges
Time Limit:1S Memory Limit:1000K
Total Submit:34 Accepted:10
Description
On the banks of the Three Gorges of the Yangtze River live some old clans. For
historical reasons, clans on the same gorge hate each other, and conflicts often arise
between them for lands and recourses. On the contrary they have a long and deep
friendship with the clans on the other gorges. But it's difficult for them to travel to the
other sides of the gorge because of the torrent flow of the Yangtze River.
One day they decide to build suspension bridges between the gorges. The gorges have
three banks (figure 1), and each bank is rolling so clans have different altitude. Every
clan will not share a same bridge with other clans on the same bank, so there must be
at least one bridge for each clan. And for safety reason, bridges are not allowed to
cross each other overhead, or if a bridge collapsed, it would fall on another one.
Experts point out that if the altitudes of the two ends of a bridge are different, the
bridge will be troublesome to build and cost more. It's estimated that the cost of a
bridge is equal to the fall of the ends of the bridge. The clans are not rich, so they
employ you to find a solution to minimize the cost to build the suspension bridges to
satisfy their demand.
