zych1751   3년 전

Recurrence: DP[i][j]=Mini≤k<j(DP[i][k]+DP[k+1][j]+C[i][j])

Condition: C[i][j] is a Monge array, and satisfies C[a][d]≥C[b][c] for a≤b≤c≤d.

출처: https://koosaga.com/243?category=554431 [구사과]

위의 조건을 만족할 때 knuth optimization을 쓸 수 있다고 하는데, 이 문제에서는 C[i][j]이 A[j] - A[k]입니다.

C[i][j]에 k가 섞여있는데 그래도 optimization이 성립하나요? 

댓글을 작성하려면 로그인해야 합니다.