볼록 다각형 삼각분할
골드 II의견: 0
꼭짓점이 \(N\) 개인 볼록 다각형의 꼭짓점들에 차례로 가중치 \(w_0, w_1, \dots, w_{N-1}\) 가 붙어 있습니다. 이 다각형을 서로 겹치지 않는 대각선들로 잘라 \(N-2\) 개의 삼각형으로 삼각분할하려고 합니다.
꼭짓점 \(i, j, k\) 로 이루어진 삼각형 하나의 비용을 \(w_i \cdot w_j \cdot w_k\) 라고 할 때, 전체 삼각형 비용의 합을 최소로 하는 삼각분할의 비용을 구하세요.
구간 DP로 "꼭짓점 \(i\) 부터 \(j\) 까지의 부분 다각형"의 최적 분할 비용을 계산하면 \(O(N^3)\) 에 해결됩니다.
- \(3 \le N \le 300\)
- \(1 \le w_i \le 200\)
첫 줄에 꼭짓점 수 \(N\) 이 주어집니다.
둘째 줄에 다각형을 한 방향으로 따라가며 만나는 꼭짓점 가중치 \(w_0, \dots, w_{N-1}\) 이 주어집니다.
최소 삼각분할 비용을 한 줄에 출력합니다.
4
1 2 3 418볼록 사각형을 두 삼각형으로 나누는 두 가지 분할 중 비용이 작은 쪽을 택합니다.
3
2 3 424삼각형은 분할이 하나뿐이며 비용은 \(2\cdot3\cdot4=24\) 입니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
볼록 다각형 삼각분할
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
볼록 다각형 삼각분할