412. The Cheapest Set of Travel Passes
You must travel on certain days of a year, given in increasing order. Passes come in three kinds, each valid for CONSECUTIVE days starting the day you buy it:
a 1-day pass costs c1
a 7-day pass costs c7
a 30-day pass costs c30
Print the least total cost that covers every travel day.
A pass may cover days you do not travel, and that is exactly what makes greedy rules fail. Buying the cheapest per-day rate is wrong when travel days cluster; buying a long pass at every cluster is wrong when the clusters are far apart.
Define dp[d] as the least cost to cover every travel day up to and including
day d. Then:
if d is not a travel day: dp[d] = dp[d-1] nothing new to cover
otherwise: dp[d] = min of
dp[d-1] + c1
dp[d-7] + c7
dp[d-30] + c30
Each option says "buy a pass that ENDS today", so it covers the window back to where the previous cost was already paid.
Clamp the lookbacks at 0 rather than skipping them. A 30-day pass bought on day
3 is legal and sometimes optimal, and dp[-27] must read as dp[0] = 0, not as
an error or a skipped option.
Constraints - `1 ≤ n ≤ 365` - `1 ≤ day ≤ 365`, strictly increasing - `1 ≤ c1, c7, c30 ≤ 1000`
Input
The first line contains four integers n, c1, c7 and c30.
The second line contains n strictly increasing travel days, each between 1 and 365.
Output
Print the least total cost covering every travel day.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.