Problem 22505 --租用游艇问 题

22505: 租用游艇问 题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][168kb]

Description

长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,…,n。游客可在这些游艇出租

站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间

的租金为 r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站 1 到游艇出租站 n 所需

的最少租金。


 

«编程任务:

对于给定的游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j),1<=i<j<=n,编程计算从

游艇出租站 1 到游艇出租站 n 所需的最少租金。


 

Input

1 行中有 1 个正整数 nn<=200),表示有 n

个游艇出租站。接下来的 n-1 行是 r(i,j),1<=i<j<=n。

Output

将计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金输出

Sample Input

3 
5 15 
7 

Sample Output

12

HINT

Source

[Submit][Status]