C++ में बहुभुज का न्यूनतम स्कोर त्रिभुजन

मान लीजिए कि हमारे पास एक मान एन है, एक उत्तल एन-पक्षीय बहुभुज पर विचार करें जिसमें ए [0], ए [i], ..., ए [एन -1] लेबल वाले शिखर दक्षिणावर्त क्रम में हैं। अब मान लीजिए कि हम बहुभुज को N-2 त्रिभुजों में त्रिभुज करना चाहते हैं। प्रत्येक त्रिभुज के लिए, उस त्रिभुज का मान शीर्षों के लेबल का गुणनफल होता है, और त्रिभुज का कुल स्कोर त्रिभुज में सभी N-2 त्रिभुजों पर इन मानों का योग होगा। हमें सबसे छोटा संभव कुल स्कोर ज्ञात करना है जिसे हम बहुभुज के कुछ त्रिभुज के साथ प्राप्त कर सकते हैं। तो अगर इनपुट [1,2,3] है, तो आउटपुट 6 होगा, क्योंकि बहुभुज पहले से ही त्रिभुज है, और एकमात्र त्रिभुज का स्कोर 6 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• 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]

• वापसी डीपी [0, एन -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