레이팅 미적용농부 존(Farmer John)의 N마리 (1 <= N <= 2000) 소들은 헛간에서 목초지로 가는 직선 길을 따라 여러 위치에 서 있다. 이 길은 1차원 수직선으로 생각할 수 있다. 소들은 서로 이메일로 연락하는 것을 좋아하므로, FJ는 모든 소가 무선 통신 범위 안에 들어오도록 여러 위치에 와이파이 기지국을 설치하고 싶어 한다.
여기저기 알아본 끝에, FJ는 와이파이 기지국의 비용이 전송 가능 거리에 따라 달라진다는 것을 알게 되었다. 출력 r의 기지국의 비용은 A + B*r이며, 여기서 A는 기지국 설치의 고정 비용이고 B는 전송 거리 단위당 비용이다. FJ가 위치 x에 이런 장치를 설치하면, x-r ... x+r 범위에 있는 모든 소에게 데이터를 전송할 수 있다. 전송 출력이 r=0인 기지국도 허용되지만, 이는 송신기와 같은 위치에 있는 소에게만 통신을 제공한다.
A와 B의 값과 FJ의 소들의 위치가 주어질 때, FJ가 모든 소에게 무선 통신을 제공할 수 있는 가장 저렴한 방법을 구하시오. (답은 57.5 같은 반정수일 수 있다.)
첫째 줄: 공백으로 구분된 세 정수 N A B (0 <= A, B <= 1000).
둘째 줄부터 1+N번째 줄까지: 각 줄에 FJ의 소 한 마리의 위치를 나타내는 0..1,000,000 범위의 정수가 주어진다.
모든 소에게 무선 통신을 제공하는 최소 비용 (정수, 또는 소수점 아래 한 자리로 출력하는 반정수. 예: 57.5).
wifi.in · 출력을 쓸 파일 wifi.out3 20 5
7
0
10057.5Input details: There are 3 cows at positions 7, 0, and 100. Installation of a base station of power r costs 20 + 5*r.
Output details: Build a base station at position 3.5 (power 3.5) covering cows 1 and 2, and another at position 100 (power 0) covering cow 3.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > December > Silver