New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1878: 奶牛的雨伞

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计

题目描述

今天是雨天！ 农夫 的 N (1 <= N <= 5,000) 头奶牛，编号为 1..N。
N头奶牛站成一排， X 坐标从 1 到 M（1 <= M <= 100,000）。
奶牛 i 站在坐标 X_i (1 <= X_i <= M) 的位置上，所有奶牛位置均不同。 
为了给奶牛挡雨，农夫约翰想给它们买把雨伞。 
一把横跨坐标 X_i 到 X_j (X_i <= X_j) 的雨伞，其宽度为 X_j - X_i + 1。
购买一把宽度为 W 的雨伞需要花费 C_W (1 <= C_W <= 1,000,000)。
更宽雨伞的花费不一定超过更窄雨伞。 
帮助农夫购买一套能保证每头奶牛不被雨淋的最低成本。
请注意，最佳解决方案中的伞和伞之间可能存在重叠。

输入格式

输入第一行为正整数 N 和 M 。
第 2 行到第 N+1 行，第 i+1 行输入一个数字表示 X_i 。
第 N+2 行到第 N+M+1 行，第 N+1+j 行输入一个数字表示 C_j。

输出格式

输出一个数字表示答案。

输入样例 复制 

6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
19

输出样例 复制 

9

数据范围与提示

购买1把宽度为4、1把宽度为2、1把宽度为1的伞即可。 
U--------U           U        U--U
C  C     C           C        C  C
|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12
其中C表示牛的位置，U---U表示伞，最小成本：2+3+4=9。
来源：USACO 2011.12