레이팅 미적용오늘은 비 오는 날이다! 농부 존(Farmer John)의 N마리 (1 <= N <= 5,000) 소들은 1..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.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 정수 X_i가 주어진다.
N+2번째 줄부터 N+M+1번째 줄까지: N+j+1번째 줄에 정수 C_j가 주어진다.
모든 소를 위한 우산을 구매하는 데 필요한 최소 비용을 나타내는 정수 하나.
umbrella.in · 출력을 쓸 파일 umbrella.out6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
199Input details: There are 12 stalls, and stalls 1, 2, 4, 8, 11, and 12 contain cows. An umbrella covering one stall costs 2, an umbrella covering two stalls costs 3, and so on.
Output details: By purchasing a size 4 umbrella, a size 1 umbrella, and a size 2 umbrella, it is possible to cover all the cows at a cost of 4+2+3=9.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Silver