C++에서 다각형의 최소 점수 삼각 측량

<시간/>

값 N이 있다고 가정하고 A[0], A[i], ..., A[N-1]이라는 레이블이 지정된 정점이 있는 볼록한 N면 다각형이 시계 방향 순서라고 가정합니다. 이제 다각형을 N-2개의 삼각형으로 삼각측량하려고 한다고 가정합니다. 각 삼각형의 경우 해당 삼각형의 값은 꼭짓점 레이블의 곱이며 삼각형의 총 점수는 삼각형의 모든 N-2개 삼각형에 대한 이러한 값의 합이 됩니다. 우리는 다각형의 일부 삼각 측량으로 얻을 수 있는 가장 작은 총점을 찾아야 합니다. 따라서 입력이 [1,2,3]이면 다각형이 이미 삼각 측량되어 있고 유일한 삼각형의 점수가 6이므로 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

50 x 50 크기의 행렬 dp를 만들고 0으로 채웁니다.
n :=주어진 배열의 크기
범위 n에서 n
에 있는 l에 대해
- for i :=0, j :=l – 1, j
  - 범위 i + 1 ~ j – 1의 k에 대해
    - dp[i, j] =0이면
      - dp[i, j] :=inf 및 dp[i, k] + dp[k, j] + A[i] * A[j] * A[k]
        의 최소값
    - 그렇지 않으면 dp[i, j] :=dp[i,j] 및 dp[i, k] + dp[k, j] + A[i] * A[j] * A[k]
      의 최소값
반환 dp[0, n – 1]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
   class Solution {
   public:
   int minScoreTriangulation(vector<int>& A) {
      lli dp[50][50];
      for(int i = 0; i < 50; i++){
         for(int j = 0; j < 50; j++){
            dp[i][j] = 0;
         }
      }
      int n = A.size();
      for(int l = 3; l <= n; l++){
         for(int i = 0, j = l - 1; j < n;i++, j++){
            for(int k = i + 1; k < j; k++){
               dp[i][j] = min(dp[i][j] == 0?INT_MAX : dp[i][j],
               dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   vector<int> v1 = {1,2,3};
   Solution ob;
   cout << (ob.minScoreTriangulation(v1));
}

입력

[1,2,3]