ऐरे का निर्माण करें जहाँ आप C++ में अधिकतम सटीक K तुलना पा सकते हैं

मान लीजिए कि हमारे पास तीन पूर्णांक n, m और k हैं। यदि हमारे पास सकारात्मक पूर्णांकों की एक सरणी के अधिकतम तत्व को खोजने के लिए निम्नलिखित एल्गोरिथम है -

max_val := -1
max_ind := -1
search_cost := 0
n := size of arr
for initialize i := 0, when i < n, update (increase i by 1), do:
   if max_val < arr[i], then:
      max_val := arr[i]
      max_ind := i
      (increase search_cost by 1)
return max_ind

हमें सरणी को एआर बनाना है जिसमें निम्नलिखित मानदंड हैं:एआर में बिल्कुल n पूर्णांक हैं। सभी तत्व गिरफ्तार [i] 1 से मी (सहित) (0 <=i

इसलिए, यदि इनपुट n =2, m =3, k =1 जैसा है, तो आउटपुट 6 होगा क्योंकि संभावित सरणियाँ हैं [1, 1], [2, 1], [2, 2], [3 , 1], [3, 2] [3, 3]

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

• मी :=10^9 + 7

• फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम

• आकार की एक सरणी dp परिभाषित करें:54 x 54 x 105।

• फ़ंक्शन सहायता () को परिभाषित करें, यह idx, m, k, currVal, n,

  लेगा

• अगर के <0, तो -

  • वापसी 0

• अगर idx n + 1 के समान है, तो -

  • जब k 0 हो तब सही लौटें

• अगर dp[idx, k, currVal + 1] -1 के बराबर नहीं है, तो -

  • वापसी dp[idx, k, currVal + 1]

• रिट:=0

• इनिशियलाइज़ करने के लिए i :=1, जब i <=m, अपडेट (i से 1 की वृद्धि), करें -

  • अगर मैं> currVal, तो -

    • ret :=add(help(idx + 1, m, k-1), max(currVal,i), n), ret)

  • अन्यथा

    • ret :=add(help(idx + 1, m, k, max(currVal,i), n), ret)

• वापसी dp[idx, k, currVal + 1] =ret

• मुख्य विधि से निम्न कार्य करें -

• इनिशियलाइज़ करने के लिए i:=0, जब i <54, अपडेट करें (1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=0 के लिए, जब j <54, अपडेट करें (j को 1 से बढ़ाएँ), करें -

    • k :=0 को इनिशियलाइज़ करने के लिए, जब k <105, अपडेट करें (1 से k बढ़ाएँ), करें -

      • डीपी [आई, जे, के] :=-1

  • रिट :=सहायता(1, एम, के, -1, एन)

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
   lli add(lli a, lli b) {
      return ((a % m) + (b % m)) % m;
   }
   int dp[54][54][105];
   int help(int idx, int m, int k, int currVal, int n) {
      if (k < 0)
         return 0;
      if (idx == n + 1) {
         return k == 0;
      }
      if (dp[idx][k][currVal + 1] != -1)
         return dp[idx][k][currVal + 1];
      int ret = 0;
      for (int i = 1; i <= m; i++) {
         if (i > currVal) {
            ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret);
         }
         else {
            ret = add(help(idx + 1, m, k, max(currVal, i), n), ret);
         }
      }
      return dp[idx][k][currVal + 1] = ret;
   }
   int numOfArrays(int n, int m, int k) {
      for (int i = 0; i < 54; i++)
         for (int j = 0; j < 54; j++)
            for (int k = 0; k < 105; k++)
               dp[i][j][k] = -1;
      int ret = help(1, m, k, -1, n);
      return ret;
   }
};
main() {
   Solution ob;
   cout << (ob.numOfArrays(2, 3, 1));
}

इनपुट

2, 3, 1

आउटपुट

6