最优路线吃鱼：寻找最小猫粮费用

明明家从 1 号站点出发，开车去旅游，一共要经过 n 个站点，依次为 2、3……n。

由于明明带上了心爱的小猫，在每个站点都要为小猫提供一条鱼用做美餐（包括 1 号站点）。

除了 1 号站点只能吃 1 号站点买的鱼，其他站点既可以吃当地买的鱼，也可吃之前经过的站点买了存入车载冰箱中的鱼。

但车载冰箱消耗的电能来自汽油，所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。

为使问题简化，我们约定：

(1) 车从某站开出时油箱中都是此站点刚加的汽油。

(2) 车载冰箱能容纳一路上需要的所有鱼。

即：每条鱼的费用既包括购买时的费用，也包括用冰箱保存鱼的费用。

编程实现：

为了降低小猫吃鱼的总代价，明明预先上网查到了这 n 个站点的鱼价和汽油价格。并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费用吗？

输入描述

第一行：站点数 n，1<n<100。

接下来的 n 行：每行两个以空格分隔的正整数，表示：这一站买一条鱼的费用，以及从这一站把每条鱼保存到下一站的费用，两个费用均为小于 10000 的正整数。

输出描述

最小总费用，是一个正整数、

代码实现 (C++)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i].first >> cost[i].second;
    }

    vector<int> dp(n, 1000000); // 初始化为一个很大的数
    dp[0] = cost[0].first; // 第一个站点只能买鱼

    for (int i = 1; i < n; i++) {
        // 从当前站点购买鱼
        dp[i] = min(dp[i], dp[i - 1] + cost[i].first);
        // 从前一个站点保存鱼到当前站点
        if (i > 1) {
            dp[i] = min(dp[i], dp[i - 2] + cost[i - 1].second + cost[i].first);
        }
    }

    cout << dp[n - 1] << endl;

    return 0;
}

解释

明明一共经过了5个站点，分别是1、2、3、4、5。

从1号站点出发，明明需要买一条鱼，费用为10。然后继续前往2号站点，此时明明需要买一条鱼，费用为20，并将之前购买的鱼保存到车载冰箱中，费用为10。

然后继续前往3号站点，此时明明需要买一条鱼，费用为15，并将之前购买的鱼保存到车载冰箱中，费用为5。

然后继续前往4号站点，此时明明需要买一条鱼，费用为30，并将之前购买的鱼保存到车载冰箱中，费用为20。

最后到达5号站点，此时明明需要买一条鱼，费用为25，并将之前购买的鱼保存到车载冰箱中，费用为15。

所以明明吃鱼的最小总费用为10+20+15+30+25+10+5+20+15=85。