1354 问题 C: 长江游艇问题

时间限制: 1s 内存限制: 128MB 提交: 13 解决: 2
题目描述

长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间(1≤i＜j≤n)的租金为r(i,j)。 编程任务： 求从游艇出租站1 到游艇出租站n所需的最少租金。

输入

第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。
接下来是n-1 行，每行表示游艇站i到i+1、i+2、.......、n的租金，即r(i,i+1)、r(i,i+2)、......、r(i,n)。

输出

两行

第1行为一个整数，表示从游艇出租站1 到游艇出租站n所需的最少租金

第2行输出从游艇出租站1 到游艇出租站n的最少总租金的路径上的各个停靠站，中间用"-->"连接，先输出第1个停靠站,即为1，最后输出第一个停靠站，即为n。如果有多种方案达成最少租金，则只输出这种方案：从起点起，尽可能选择最近的出租站以归还游艇并重新租借游艇。

例如：输入数据为

3

5 12

7

则： 1-->2-->3和1-->3这两种方案都可以达到最少租金，但此题要求只输出1-->2-->3这种方案。

样例输入
3
5 15
7
样例输出
12
1-->2-->3
提示
无

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
大家先把题目熟悉一下，这些题目都有一定难度，今天或明天晚上会作个动态规划的讲课和讲解。
另外，要先把回溯法复习一下，因为我的动态规划讲解，是基于对回溯法的优化的角度来讲的。
                        

                    

                

                

                    

                        
比赛状况