Luobuyu's Blog

0%

983. 最低票价

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.7k 阅读时长 ≈ 2 分钟
类似前两题，都是需要考虑反向dp的，而且要注意区别。水果和这个题都是必须要买，而考试题那个不需要。

983.最低票价

题目描述：

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

  • 一张 为期一天 的通行证售价为 costs[0] 美元；
  • 一张 为期七天 的通行证售价为 costs[1] 美元；
  • 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

数据范围：

$1\le days.len \le 365, 1\le days[i] \le 365$

days 按照顺序严格递增

题解：

当前买与不买对后面会造成影响。因此考虑加状态，或者换方式dp。

加状态：

使用 $dp[i][0/1/2/3]$ 表示第 $days[i]$ 天不买，买 $1$ 天，买 $7$ 天，买 $30$ 天的车票。需要使用二分查找找出来是否存在 $days[i] - 1/7/30$ 。

换方式dp：

从后往前，设 $dp[i]$ 表示从 $days[i]$ 到最后一天的最小花费。则第 $days[i]$ 天必须要买一张票，可以枚举买的是哪一种类型的票。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const int INF = 0x3f3f3f3f;
    // 找大于等于 target 的
    int getIndex(vector<int> &days, int start, int target)
    {
        int index = lower_bound(days.begin() + start, days.end(), target) - days.begin();
        return index;
    }
    int getIndex2(vector<int> &days, int end, int target)
    {
        int index = lower_bound(days.begin(), days.begin() + end, target) - days.begin();
        return index;
    }
    int mincostTickets(vector<int> &days, vector<int> &costs)
    {
        int n = days.size();
        int m = costs.size();
        // dp[i] i -> 最后
        // dp[i] = dp[i + 1] dp[i + 7] dp[i + 30]
        vector<vector<int>> dp(n + 1, vector<int>(4, INF));
        dp[0][1] = costs[0];
        dp[0][2] = costs[1];
        dp[0][3] = costs[2];
        for (int i = 1; i < n; ++i)
        {
            dp[i][0] = min(dp[i][0], dp[getIndex2(days, i, days[i] - 1 + 1)][1]);
            dp[i][0] = min(dp[i][0], dp[getIndex2(days, i, days[i] - 7 + 1)][2]);
            dp[i][0] = min(dp[i][0], dp[getIndex2(days, i, days[i] - 30 + 1)][3]);
            int tmp = min(dp[i - 1][0], min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])));
            dp[i][1] = tmp + costs[0];
            dp[i][2] = tmp + costs[1];
            dp[i][3] = tmp + costs[2];
        }
        return min(dp[n - 1][0], min(dp[n - 1][1], min(dp[n - 1][2], dp[n - 1][3])));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const int INF = 0x3f3f3f3f;
    // 找大于等于 target 的
    int getIndex(vector<int> &days, int start, int target)
    {
        int index = lower_bound(days.begin() + start, days.end(), target) - days.begin();
        return index;
    }
    int mincostTickets(vector<int> &days, vector<int> &costs)
    {
        int n = days.size();
        int m = costs.size();
        // dp[i] i -> 最后
        // dp[i] = dp[i + 1] dp[i + 7] dp[i + 30]
        vector<int> dp(n + 1, INF);
        dp[n] = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            // 买
            dp[i] = min(dp[i], costs[0] + dp[getIndex(days, i, days[i] + 1)]);
            dp[i] = min(dp[i], costs[1] + dp[getIndex(days, i, days[i] + 7)]);
            dp[i] = min(dp[i], costs[2] + dp[getIndex(days, i, days[i] + 30)]);
        }
        return dp[0];
    }
};