#655. 地宫勇者小码君
地宫勇者小码君
题目描述
勇者小码君为了拯救整个被蜘蛛女皇所恐怖统治的阿拉德大陆,来到了蜘蛛女皇的地下行宫讨伐蜘蛛女皇,蜘蛛女皇在地下行宫的最深处。地宫一共深n+1层,前n层第i层有i处通往下一层的入口,每个入口处都有小兵把守,我们需要尽可能的节省勇者小码君的体力,让他在找到蜘蛛女皇前碰到的小兵的数量尽可能少,小码君只能沿着红色的路线(左下或者右下)向下一层探索,蜘蛛女皇的5层地宫图如下。
每个正方形方块代表一个通往下一层的据点,里面的数字代表小兵的数量,解决掉每一个小兵所耗费的体力为1,只能沿着红色路径(左下或者右下)向下一层探索,输出津津在找到蜘蛛女皇时所耗费的最小体力。
输入格式
第1行输入一个正整数n,表达到达最底层之前的地宫层数
接下来输入n行数据
第1行输入1个数据表示据点的小兵数量
第2行输入2个数据表示据点的小兵数量
……………………
第n行输入n个数据表示据点的小兵数量
输出格式
一个整数n,表示津津在找到蜘蛛女皇时所耗费的最小体力。
样例
样例输入
4
6
5 8
3 1 9
6 2 4 3
样例输出
14