Problem Q: 小猫吃鱼(fish)
[Creator : ]
Description
明明家从 1 号站点出发,开车去旅游,一共要经过 n 个站点,依次为 2、3……n。
由于明明带上了心爱的小猫,在每个站点都要为小猫提供一条鱼用做美餐(包括 1 号站点)。
除了 1 号站点只能吃 1 号站点买的鱼,其他站点既可以吃当地买的鱼,也可吃之前经过的站点买了存入车 载冰箱中的鱼。
但车载冰箱消耗的电能来自汽油,所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。
为使问题简化,我们约定:
(1)车从某站开出时油箱中都是此站点刚加的汽油。
(2)车载冰箱能容纳一路上需要的所有鱼。
即:每条鱼的费用既包括购买时的费用,也包括用冰箱保存鱼的费用。
为了降低小猫吃鱼的总代价,明明预先上网查到了这 n 个站点的鱼价和汽油价格。并据此算出每个站点买 一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费 用吗?
由于明明带上了心爱的小猫,在每个站点都要为小猫提供一条鱼用做美餐(包括 1 号站点)。
除了 1 号站点只能吃 1 号站点买的鱼,其他站点既可以吃当地买的鱼,也可吃之前经过的站点买了存入车 载冰箱中的鱼。
但车载冰箱消耗的电能来自汽油,所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。
为使问题简化,我们约定:
(1)车从某站开出时油箱中都是此站点刚加的汽油。
(2)车载冰箱能容纳一路上需要的所有鱼。
即:每条鱼的费用既包括购买时的费用,也包括用冰箱保存鱼的费用。
为了降低小猫吃鱼的总代价,明明预先上网查到了这 n 个站点的鱼价和汽油价格。并据此算出每个站点买 一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费 用吗?
Input
第一行:站点数 $n\ (1<n<100)$。
接下来的 $n$ 行:每行两个以空格分隔的正整数,表示:这一站买一条鱼的费用,以及从这一站把每条 鱼保存到下一站的费用,两个费用均为小于 $10,000$ 的正整数。
接下来的 $n$ 行:每行两个以空格分隔的正整数,表示:这一站买一条鱼的费用,以及从这一站把每条 鱼保存到下一站的费用,两个费用均为小于 $10,000$ 的正整数。
Output
最小总费用,是一个正整数。
Sample 1 Input
5
6 3
7 1
3 2
8 3
9 5
Sample 1 Output
29
1 号站,小猫吃鱼花费 6 元。
2 号站,小猫吃鱼花费 7 元。
3 号站,小猫吃鱼花费 3 元。
4 号站,小猫吃鱼花费 3 + 2 = 5 元(因为 3 + 2 < 8)。
5 号站,小猫吃鱼花费 5 + 3 = 8 元(因为 5 + 3 < 9)。
共 6 + 7 + 3 + 5 + 8 = 29 元
2 号站,小猫吃鱼花费 7 元。
3 号站,小猫吃鱼花费 3 元。
4 号站,小猫吃鱼花费 3 + 2 = 5 元(因为 3 + 2 < 8)。
5 号站,小猫吃鱼花费 5 + 3 = 8 元(因为 5 + 3 < 9)。
共 6 + 7 + 3 + 5 + 8 = 29 元