题目描述

租用游艇

题目描述

长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\cdots,n$。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r(i,j)$（$1\le i\lt j\le n$）。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

输入格式

第一行中有一个正整数 $n$，表示有 $n$ 个游艇出租站。接下来的 $n-1$ 行是一个半矩阵 $r(i,j)$（$1\le i<j\le n$）。

输出格式

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

样例 #1

样例输入 #1

3
5 15
7

样例输出 #1

12

提示

$n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。

=分界线======

希蒙准备刷 $n$ 道水题 $1,2,\cdots,n$。作为爱学习的人，他已经成功把第一题完成，接下来希蒙可以直接刷任意一道水题，不过作为有强迫症的希蒙，他做题有几个要求：

• 做了第i号题后，他之后做的题目编号一定大于i

• 他一定要做第n号题目，其余题目都是可选完成

现在给出完成第 $i$ 号题后再去做 $j$ 号题目的时间为 $r(i,j)$（$1\le i\lt j\le n$）。试设计一个算法，计算出完成第 $n$ 题目所需的最少时间。

输入格式

第一行中有一个正整数 $n$，表示有 $n$ 道题目。

接下来的 $n-1$ 行是一个半矩阵 $r(i,j)$（$1\le i<j\le n$）

第2行表示完成第一题后再去做第$2,3, \cdots,n$号题花费的时间

第3行表示完成第二题后再去做第$3,4, \cdots,n$号题花费的时间

.....

第n行表示完成第n-1题后再去做第$n$题花费的时间

输出格式

输出计算出完成第 $n$ 号题的最少时间。

输入输出样例 #1

输入 #1

5
2 3 9 12
4 1 9
8 8
4

输出 #1

7

说明/提示

样例解读

这里选择选完成第2题花费时间2，然后再完成第4题花费时间1，最后完成第5题花费时间4，总耗时7

$n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。