C++でのポリゴンの最小スコア三角分割

値Nがあるとすると、A [0]、A [i]、...、A[N-1]というラベルの付いた頂点が時計回りに並んでいる凸多角形を考えます。ここで、ポリゴンをN-2個の三角形に三角形分割するとします。各三角形について、その三角形の値は頂点のラベルの積であり、三角形分割の合計スコアは、三角形分割内のすべてのN-2三角形のこれらの値の合計になります。ポリゴンの三角形分割で達成できる最小の合計スコアを見つける必要があります。したがって、入力が[1,2,3]の場合、ポリゴンはすでに三角形分割されており、唯一の三角形のスコアは6であるため、出力は6になります。

これを解決するには、次の手順に従います-

• サイズ50x50の行列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]

出力

6