179 人解决,201 人已尝试。
235 份提交通过,共有 628 份提交。
2.4 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
给定 $n$ 个点,$m$ 个操作,每次操作可以将第 $L_i$ 个点到第 $R_i$ 个点覆盖,耗费是 $W_i$。
问至少覆盖(可以重复覆盖) $k$ 个点的最小耗费是多少?
第 1 行:一个整数 $T (1\leq T\leq 10)$ 为问题数。
接下来 $T$ 组测试数据,每组测试数据按如下格式输入:
第一行包含 3 个整数 $n,m,k(1\le n \le 300, 1\le m\le 10^5,1\le k\le n)$。
接下来 $m$ 行,每行包含 3 个整数 $L_i,R_i,W_i(1\le L_i \le R_i \le n,1 \le W_i \le 10^9)$
对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0:
等)。
然后对应每个问题 , 在一行中输出最小耗费,如果不能覆盖 k 个点输出 -1。
3 10 4 6 7 9 11 6 9 13 7 7 7 3 5 6 10 7 1 3 4 15 8 9 8 5 6 8 9 10 6 1 4 2 1 4 10 8 10 13 10 5 5 7 9 18 3 6 12 1 2 4 5 7 5 6 10 30
case #0: 17 case #1: 2 case #2: 9
179 人解决,201 人已尝试。
235 份提交通过,共有 628 份提交。
2.4 EMB 奖励。
创建: 8 年,4 月前.
修改: 6 年,11 月前.
最后提交: 3 月,3 周前.
来源: N/A