4518. Minimum ticket price

In a country where train travel is very popular , You planned some train trips a year in advance .

In the next year , The day you are going to travel will be called days The array of gives .

Each item is from 1 To 365 The integer of .

There are three different ways of selling train tickets ：

A one-day pass costs costs[0] dollar ;
A seven day pass costs costs[1] dollar ;
A 30 day pass costs costs[2] dollar .
The pass allows unlimited travel for days .

for example , If we were in 2 Days to get a duration of 7 Day's pass , Then we can travel together 7 God ： The first 2 God 、 The first 3 God 、 The first 4 God 、 The first 5 God 、 The first 6 God 、 The first 7 Day and day 8 God .

Return what you want to complete in the given list days The minimum cost of travel for each day listed in .

Input format

The first line contains an integer n, Express days Length of array .

The second line contains n It's an integer , Express days[i].

The third line contains 3 It's an integer , Express costs[i].

Output format

An integer , Indicates the minimum consumption required for travel .

Data range

1≤n≤365,
1≤days[i]≤365,
days Strictly increasing in order ,
1≤costs[i]≤1000.

sample input ：

6
1 4 6 7 8 20
2 7 15

sample output ：

11

Code ：

/* f [ i ]  For the former  i  Days , Minimum cost required   We can divide sets into three categories ： （1） On this day  days [ i ]  Buy a one-day ticket alone , The answer is  f [ i ] = f [ i - 1 ] + costs [ 0 ]; （2） Find out about the current  i  The difference between the latest and just enough days is more than  7  Subscript of day  j, Then the front cost is f [ j ],  Plus the expenses in the last seven days costs [ 1 ],  namely  f [ i ] = f [ j ] + costs [ 1 ]; （3） Find out about the current  i  The difference between the latest and just enough days is more than  30  Subscript of day  k, Then the front cost is f [ k ],  Plus the expenses in the last 30 days costs [ 2 ],  namely  f [ i ] = f [ k ] + costs [ 2 ];  Yes  2  Three situations in , We take a minimum value is the answer  */
#include <bits/stdc++.h>
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)//  Go back to find the closest to the current subscript and just meet the number of days, with a difference of more than limit The subscript ,  But the limit is  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;
}