10067번 - 수열 나누기
$dp[t][i] = \max(dp[t - 1][j] + (S_i - S_j)S_j$로 정의한 경우 $j < i$이어야 하므로 $i \le n - (k - t)$인 $i$에 대해서만 계산하여 직선을 넣어주고 답이 되는 가장 큰 인덱스를 추적하도록 하면 인덱스를 역추적 할 때 마지막으로 나눈 인덱스보다 항상 작은 인덱스를 얻을 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
skuru 1년 전
$dp[t][i] = \max(dp[t - 1][j] + (S_i - S_j)S_j$로 정의한 경우 $j < i$이어야 하므로 $i \le n - (k - t)$인 $i$에 대해서만 계산하여 직선을 넣어주고 답이 되는 가장 큰 인덱스를 추적하도록 하면 인덱스를 역추적 할 때 마지막으로 나눈 인덱스보다 항상 작은 인덱스를 얻을 수 있습니다.