TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1263
  • 题目
  • P1263小猪上山
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    这一天,小猪来到了一座深山的山脚下,他要拜访这座深山中的一位隐者。但是上山的路错综复杂。小猪想找一条需时最少的路到达山顶,但现在它一头雾水,所以向你求助。
    山用一个三角形表示,从山顶依次向下有1段、2段、3段等山路,每一段用一个数字T(1<=T<=100)表示,代表晴天小猪在这一段山路上需要爬的时间,每一次它都可以朝左、右、上、右上四个方向走(注意:在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段)。
    小猪从山的左下角出发,目的地为山顶,即隐者的小屋。

    输入格式

    第一行有一个数n(2<=n<=1000),表示山的高度。
    从第二行至第n+1行,第i+1行有i个数,每个数表示小猪在这一段山路上需要爬的时间。

    输出格式

    一个数,即小猪所需要的最短时间。

    样例输入

    5
    1
    2 3
    4 5 6
    10 1 7 8
    1 1 4 5 6

    样例输出

    10