[BOJ] 16119번: Cherrypick

https://www.acmicpc.net/problem/16119


1. 최대 $32 \times 32$의 칸까지만 고려하면 된다.


2. $D[t][i][j]$를 $(i, j)$를 오른쪽 구석으로 하는 $t \times t$ 사각형에서의 체리의 당도중 최댓값이라고 할 때 $D[t][i][j] = max(D[t-1][i-1][j], D[t-1][i][j-1], C[i][j], C[i-t+1][j-t+1])$이다.


이 사실을 이용해 D 테이블을 다 채우면 $O(32NM)$에 답을 구할 수 있습니다.


https://github.com/blisstoner/BOJ/blob/master/16119.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1939번: 중량제한  (0) 2019.02.13
[BOJ] 15683번: 감시  (2) 2019.02.06
[BOJ] 15686번: 치킨 배달  (0) 2019.02.06
[BOJ] 12895번: 화려한 마을  (0) 2019.01.14
[BOJ] 1477번: 휴게소 세우기  (0) 2019.01.14
[BOJ] 2461번: 대표 선수  (0) 2019.01.13
  Comments