레이팅 미적용RiseOJ의 예비 채점 서버는 \(N\)초 동안 동작한다. 매초 서버의 전압 단계를 \(0\), \(1\), \(2\) 중 하나로 설정해야 한다.
\(i\)초에 전압 단계를 \(v\)로 설정하는 비용은 \(C_{i,v}\)이다. 서버를 보호하기 위해 인접한 두 시각의 전압 단계 차이는 \(1\) 이하여야 한다.
즉, 선택한 전압 단계를 \(x_1,x_2,\ldots,x_N\)이라고 하면 다음을 만족해야 한다.
$$ |x_i-x_{i-1}|\le 1 \qquad (2\le i\le N) $$
총비용을 최소화하고, 그 최소비용을 만드는 전압 단계 기록 하나를 출력하여라. 최적 기록이 여러 개라면 그중 아무거나 출력해도 된다.
- \(1 \le N \le 200\,000\)
- \(0 \le C_{i,v} \le 10^9\)
- 모든 입력은 정수이다.
- 최소비용은 64비트 정수 범위에 들어간다.
첫째 줄에 동작 시간 \(N\)이 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에 세 정수 \(C_{i,0}\), \(C_{i,1}\), \(C_{i,2}\)가 주어진다.
첫째 줄에 가능한 총비용의 최솟값을 출력한다.
둘째 줄에 그 최솟값을 만드는 전압 단계 \(x_1,x_2,\ldots,x_N\)을 공백으로 구분하여 출력한다.
최적 기록이 여러 개라면 그중 아무거나 출력해도 된다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 | \(1 \le N \le 9\) |
Subtask 2 | 80점 | 추가 제한이 없다. |
3
1 5 9
9 1 9
9 5 1
3
0 1 2
전압 단계 \(0,1,2\)를 선택하면 인접 차이가 모두 1이고 총비용은 \(1+1+1=3\)이다.
1
4 1 4
1
1
전압 단계 1을 선택하는 비용 1이 최소이다.
rip 작성
출처 RiseOJ Original