AT_abc325_f [ABC325F] Sensor Optimization Dilemma

题目描述

你作为 Keyence 工厂的厂长，想要通过传送带上的传感器来监控若干个区间。你希望监控的区间共有 $N$ 个，第 $i$ 个区间的长度为 $D_i$ 米。

传感器有两种类型可供选择，每种传感器的信息如下：

• 传感器 $j\ (1\leq j\leq 2)$：可以监控长度为 $L_j$ 米的区间。每个传感器的价格为 $C_j$，且最多可以使用 $K_j$ 个。

你可以将一个区间分割成若干部分分别进行监控。传感器监控的区间可以重叠，也可以覆盖超过需要监控的长度，这些都没有问题。例如，当 $L_1=4,L_2=2$ 时，可以用一个 1 号传感器监控长度为 $3$ 米的区间，也可以用一个 1 号和一个 2 号传感器分别监控长度为 $5$ 米的区间。

请判断是否可以监控所有 $N$ 个区间，如果可以，求出所需传感器价格总和的最小值。

输入格式

输入按以下格式从标准输入中给出。

$N$ $D_1$ $D_2$ $\dots$ $D_N$ $L_1$ $C_1$ $K_1$ $L_2$ $C_2$ $K_2$

输出格式

如果无法监控所有 $N$ 个区间，则输出 -1；如果可以，输出所需传感器价格总和的最小值。

输入输出样例 #1

输入 #1

3
3 5 10
4 3 3
2 2 6

输出 #1

17

输入输出样例 #2

输入 #2

3
3 5 10
4 3 3
2 2 3

输出 #2

-1

输入输出样例 #3

输入 #3

2
4 8
3 1 100
4 10000 100

输出 #3

5

说明/提示

限制条件

• $1\leq N\leq 100$
• $1\leq D_i, L_j\leq 10^5$
• $1\leq C_j\leq 10^9$
• $1\leq K_j\leq 10^3$
• 输入均为整数

样例解释 1

如下所示，可以使用 3 个 1 号传感器和 4 个 2 号传感器监控所有区间。

• 用 1 个 1 号传感器监控第 1 个区间。
• 用 1 个 1 号和 1 个 2 号传感器监控第 2 个区间。
• 用 1 个 1 号和 3 个 2 号传感器监控第 3 个区间。 此时所需传感器价格总和为 $3\times 3 + 2\times 4 = 17$，这是最小值。

样例解释 3

可以有某种类型的传感器一个都不使用。

由 ChatGPT 4.1 翻译