สามเหลี่ยมคะแนนขั้นต่ำของรูปหลายเหลี่ยมใน C++

สมมติว่าเรามีค่า N ให้พิจารณารูปหลายเหลี่ยมด้าน N นูนที่มีจุดยอดกำกับว่า A[0], A[i], ..., A[N-1] อยู่ในลำดับตามเข็มนาฬิกา ทีนี้ สมมติว่าเราต้องการหารูปหลายเหลี่ยมเป็นรูปสามเหลี่ยม N-2 สำหรับแต่ละสามเหลี่ยม ค่าของสามเหลี่ยมนั้นเป็นผลคูณของฉลากของจุดยอด และคะแนนรวมของสามเหลี่ยมจะเป็นผลรวมของค่าเหล่านี้จากสามเหลี่ยม N-2 ทั้งหมดในรูปสามเหลี่ยม เราต้องหาคะแนนรวมที่น้อยที่สุดเท่าที่จะเป็นไปได้โดยใช้รูปสามเหลี่ยมของรูปหลายเหลี่ยม ดังนั้นหากอินพุตเป็น [1,2,3] ผลลัพธ์จะเป็น 6 เนื่องจากรูปหลายเหลี่ยมมีสามเหลี่ยมแล้ว และคะแนนของสามเหลี่ยมเดียวคือ 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างเมทริกซ์ dp ขนาด 50 x 50 เติมด้วย 0

• n :=ขนาดของอาร์เรย์ที่กำหนด

• สำหรับ l อยู่ในช่วง n ถึง n

  • สำหรับ i :=0, j :=l – 1, เมื่อ j

    • สำหรับ k ในช่วง i + 1 ถึง j – 1

      • ถ้า 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