Олимпиадный тренинг

Задача . Umbrellas for Cows


Задача

Темы: дп

Сегодня - дождь.! N (1 <= N <= 5,000) коров Фермера Джона, пронумерованные от 1 до N не хотят мокнуть. Но они стоят в стойлах без крыш. Сойла расположены на прямой, с X_координатой от 1 до M (1 <= M <= 100,000). Корова i расположена в стойле с координатой Xi (1<=Xi<=M) . Никакие две коровы не стоят в одном стойле.
Для того, чтобы защитить коров от дождя, ФД хочет купить им зонтики. Один зонтик, который расположен от координаты Xi до координаты Xj (Xi<=Xj) имеет ширину (Xj-Xi+1). CW (1 <= CW <= 1,000,000) - цена зонтика шириной W. Необязательно, что более широкий зонтик стоит дороже более узкого.
Помогите ФД определить минимальную сумму, которую ФД должен потратить на покупку зонтиков, чтобы защитить от дождя всех своих коров.
PROBLEM NAME: umbrella
Формат входных данных
* Строка 1: Два разделенных пробелами целых числа: N M.
* Строки 2..N+1: Строка i+1 содержит одно целое число: Xi.
* Строки N+2..N+M+1: Строка N+j+1 содержит одно целое число: Cj.
Формат выходных данных
* Строка 1: Одно целое число - минимальная стоимость покупки зонтиков для покрытия всех коров.


Примечание
При покупке зонтиков с размерами 4, 1 и 2, можно покрыть всех коров и это будет стоить 9 (4+2+3=9)
UUUUUUUUUU U UUUU C C C C C C |--|--|--|--|--|--|--|--|--|--|--| 1 2 3 4 5 6 7 8 9 10 11 12
C представляет корову, U представляет часть зонтика.


Примеры
№Входные данныеВыходные данные
1 
6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
19
 
9
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет