题目描述

Wonderland是小王居住地一家很受欢迎的游乐园。Wonderland目前有 $4$ 种售票方式,分别为一日票(天)、三日票( $3$ 天)、周票( $7$ 天)和月票( $30$ 天) 。

每种售票方式的价格由一个数组给出，每种票据在票面时限内可以无限制地进行游玩。例如：

思路：动态规划

我们可以定义$f[i]$为前$i$天游玩的最小花费，首先我们需要将所有的$i(0\le i\le 365)$为正无穷，然后初始化$f[0]=0$

对于第$i$天，有两种情况

• 情况1：第$i$天不位于计划游玩日期数组中，那么很显然有状态转移方程$f[i]=f[i-1]$
• 情况2：第$i$天位于计划游玩日期数组中，由于我们有四种买票方式，因此就可以分四种情况讨论

情况2.1：在第$i$天当天购买一日票，对应的开销为$f[i-1]+costs[0]$