983. 最低票价

Powered by:NEFU AB-IN

Link

983. 最低票价

题意

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

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

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

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

思路

灵神的思路：https://leetcode.cn/problems/minimum-cost-for-tickets/solutions/2936177/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-tkw4/?envType=daily-question&envId=2024-10-01

我的思路麻烦，首先是定义两个变量，一个是多少天，一个是下标到哪了

每到一个状态，判断是否加cost的标准，就是二分找到的下一个index的坐标，比当前的大
比如 days = [1, 5]
day = 2时，下标为1（因为比days[0] = 1大），所以要加cost[0]，算是days[0]的门票，dfs(index = 1, day = 3)
day = 3时，下标还是为1，这时候就不加cost了

代码

# 3.8.9 import
import bisect
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)# Set recursion limit
setrecursionlimit(int(2e9))class Arr:array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])graph = staticmethod(lambda size=N: [[] for _ in range(size)])class Math:max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)class Std:pass# ————————————————————— Division line ——————————————————————class Solution:def mincostTickets(self, days: List[int], costs: List[int]) -> int:@lru_cache(None)def dfs(index: int, day: int):if index == len(days):return 0day_1 = day + 1day_7 = day + 7day_30 = day + 30ans = INFindex_1 = bisect.bisect_left(days, day_1)index_7 = bisect.bisect_left(days, day_7)index_30 = bisect.bisect_left(days, day_30)ans = Math.min(ans, dfs(index_1, day_1) + (costs[0] if index_1 > index else 0))ans = Math.min(ans, dfs(index_7, day_7) + (costs[1] if index_7 > index else 0))ans = Math.min(ans, dfs(index_30, day_30) + (costs[2] if index_30 > index else 0))return ansreturn dfs(0, days[0])