最低票价

/******************************************************************************
 * algo > DP
 *      > 约定 days[] 1-index, costs[] 0-index
 *      > (以下的 i 等序号默认指 days[i], 即第 i 个给出的日期)
 *        f[i]: 完成 days[1..i] 的旅行所需要的最低消费
 *        f[i] = min{f[p[i][0]] + costs[0],
 *                   f[p[i][1]] + costs[1],
 *                   f[p[i][2]] + costs[2]}, i >= 1
 *            p[i][0] 是从第 i 个日期往前数, 到哪个日期恰好超过 1 天
 *            p[i][1], p[i][2] 同理, 对应 7 天, 30 天的通行证
 *        f[0] = 0
 *      > p[i][.] 可以通过双指针计算
 * note > 该算法应该在 days 有重复时也正确
 *****************************************************************************/
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

const int kMaxN = 365;
const int kCostsLen = 3;
const int kPermitLen[] = {1, 7, 30};
const int kInf = 0x3fffffff;

int days[kMaxN+5];
int costs[kCostsLen];

int f[kMaxN+5];
int p[kMaxN+5][kCostsLen];

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> days[i];
	// 保证 days[i] 递增
	sort(days+1, days+n+1);
	for (int i = 0; i < kCostsLen; i++)
		cin >> costs[i];

	// 计算 p[][]
	for (int j = 0; j < kCostsLen; j++) {
		int l = 0;
		for (int i = 1; i <= n; i++) {
			while (days[i]-days[l+1]+1 > kPermitLen[j])
				l++;
			p[i][j] = l;
		}
	}

	// DP
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		f[i] = kInf;
		for (int j = 0; j < kCostsLen; j++) {
			f[i] = min(f[i], f[p[i][j]] + costs[j]);
		}
	}
	cout << f[n] << '\n';

	return 0;
}