BOJ 20984 : Growing Vegetables is Fun 4
2021. 5. 11. 01:31ㆍPS/DP
BOJ 20984 : Growing Vegetables is Fun 4
20984번: Growing Vegetables is Fun 4
Bitaro likes gardening. He is now growing plants called Biba-herbs in the garden. There are N Biba-herbs in the garden, planted in a line from the west to the east. The Biba-herbs are numbered from 1 to N from the west to the east. Now, the height of the B
www.acmicpc.net
Prefix-sum을 이용해 풀 수 있다.
ldp_i : 1~i번째 배추까지 증가 상태를 유지할때 필요한 최소 물의 양
rdp_i : n-i~n번째 배추까지 감소 상태를 유지할때 필요한 최소 물의 양
이라고 정의할 때
우리는 ldp, rdp의 값들을 Prefix-sum을 이용해 구한 후,
증감 상태가 바뀌는 지점을 j라고 한다면
답은 min(ldp_j, rdp_j) (1<j<=n)이 된다.
이는 O(n)으로 가능하다.
'PS > DP' 카테고리의 다른 글
| BOJ 22348 : 헬기 착륙장 (0) | 2021.07.31 |
|---|---|
| BOJ 1056 : 수 (2) | 2021.07.29 |
| BOJ 2618 : 경찰차 (1) | 2021.04.30 |
| BOJ 11570 : 환상의 듀엣 (0) | 2021.04.30 |
| BOJ 14728 : 벼락치기 (0) | 2021.01.10 |