4518. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。

在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。

每一项是一个从 1 到 365 的整数。

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

一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。

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

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

输入格式

第一行包含一个整数 n，表示 days 数组的长度。

第二行包含 n 个整数，表示 days[i]。

第三行包含 3 个整数，表示 costs[i]。

输出格式

一个整数，表示旅行所需要的最低消费。

数据范围

1≤n≤365,
1≤days[i]≤365,
days 按顺序严格递增，
1≤costs[i]≤1000。

输入样例：

6
1 4 6 7 8 20
2 7 15
1
2
3

输出样例：

11
1

代码：

/*
f [ i ] 表示对于前 i 个天数，所需要的最小花费
我们可以将集合分成三类：
（1）当前这一天 days [ i ] 单独买一张一天的票，那答案就是 f [ i ] = f [ i - 1 ] + costs [ 0 ];
（2）找到对于当前 i 最近的且刚好满足天数相差超过 7 天的下标 j，则前面的花费就是f [ j ]，
再加上这最近七天内的花费costs [ 1 ]， 即 f [ i ] = f [ j ] + costs [ 1 ];
（3）找到对于当前 i 最近的且刚好满足天数相差超过 30 天的下标 k，则前面的花费就是f [ k ]，
再加上这最近三十天内的花费costs [ 2 ]， 即 f [ i ] = f [ k ] + costs [ 2 ];
对 2 中的三种情况，我们取一个最小值就是答案
*/
#include 
using namespace std;
const int N = 400;
int n;
int d[N], f[N], c[3];

int find(int r, int limit)
{
    int l = r;
    while (l && d[r] - d[l] + 1 <= limit)// 往回找到与当前下标最接近的且刚好满足天数相差超过limit的下标, 但极限就是 1
        l--;

    return l;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    for (int i = 0; i < 3; i++)
        cin >> c[i];

    int res1, res2;

    for (int i = 1; i <= n; i++)
    {
        f[i] += f[i - 1] + c[0];
        res1 = f[find(i, 7)] + c[1];
        res2 = f[find(i, 30)] + c[2];

        int t = min(res1, res2);
        f[i] = min(f[i], t);
    }

    cout << f[n] << endl;
    
    return 0;
}
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
46
47
48
49