화물열차 서브태스크 2초 1024MB
문제
화물열차의 운행 노선은 일자 형태의 노선으로 N개의 역이 1번 역, .. , N번 역 까지 나열되어 있으며 i번 역과 i+1번 역 사이가 선로로 연결되어 있다. (역과 역 사이의 거리는 1이다.)
초기 상태는 2번 역 부터 N번 역까지 역마다 화물이 하나씩 놓여 있고 i번 역에 있는 화물의 가치는 Ai이다.
화물열차는 1번 역에서 출발하며 양방향으로 움직일 수 있다.
각 역에서 그 역에 있는 화물을 열차에 올리거나, 열차에 있는 화물을 그 역에 내릴 수 있다.
단, 무제한으로 열차에 화물을 올릴 수 없고 W개 이하의 화물만 올릴 수 있다.
또한 연료에 제한이 있어 총 이동 거리가 D이하가 되어야 한다.
최대한 가치가 높은 화물들을 1번 역으로 옮기고 싶다. 1번 역으로 옮길 수 있는 최대 화물 가치를 출력하시오.
입력
첫 번째 줄에 역의 수 N과 무게 제한 W와 연료 제한 D가 공백을 구분으로 주어진다.
그 다음 N-1개의 (2≤i≤N) Ai가 주어진다. 즉 2번 역부터 N번 역까지 각 역에 있는 화물의 가치가 들어온다.
(2 ≤ N ≤ 450)
(1 ≤ W ≤ N - 1)
(2 ≤ D ≤ N2-N)
(1 ≤ Ai ≤ 1,000,000 (2≤i≤N) )
(모든 입력 값은 정수)
출력
1번 역으로 옮길 수 있는 최대 화물 가치를 출력하시오.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 6점 | W=1, Ai=1 (2≤i≤N) |
| #2 | 9점 | Ai=1 (2≤i≤N) |
| #3 | 24점 | W=1 |
| #4 | 13점 | N≤15 |
| #5 | 24점 | N≤50 |
| #6 | 24점 | 추가 제약 조건 없음 |
예제 #1
4 1 10
1 1 1
2
다음과 같은 순서로 답을 얻을 수 있다.
1번 역->2번 역(올림)->1번 역(내림)->4번 역(올림)->1번 역(내림)
열차가 이동한 거리는 총 8이며 D 이하를 만족하고 있으며 1번 역에 내린 화물의 가치 합은 2이다.
예제 #2
7 3 16
1 1 1 1 1 1
5
다음과 같은 순서로 답을 얻을 수 있다.
1번 역->5번 역(올림)->6번 역(올림)->1번 역(모두 내림)->2번 역(올림)->3번 역(올림)->4번 역(올림)->1번 역(모두 내림)
열차가 이동한 거리는 총 16으로 D 이하를 만족하고 있으며 1번 역에 내린 화물의 가치 합은 5이다.
예제 #3
5 2 12
40 30 20 10
100
다음과 같은 순서로 답을 얻을 수 있다.
1번 역->5번 역(올림)->4번 역(올림)->2번 역(모두 내린 후 화물 40 하나 올림)->3번 역(올림)->1번 역(모두 내림)->2번 역(모두 올림)->1번 역(모두 내림)
열차가 이동한 거리는 총 12으로 D 이하를 만족하고 있으며 1번 역에 내린 화물의 가치 합은 100이다.
예제 #4
5 1 11
2 7 1 8
10
예제 #5
9 3 14
54640 754112 604290 105866 591907 801383 502975 379373
2214425
로그인해야 코드를 작성할 수 있어요.