[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