C++ में सभी मान्य पिकअप और डिलीवरी विकल्पों की गणना करें

मान लीजिए कि हमारे पास n ऑर्डर की एक सूची है, प्रत्येक ऑर्डर में पिकअप और डिलीवरी सेवाएं हैं। हमें सभी वैध पिकअप/डिलीवरी संभावित अनुक्रमों को गिनना होगा जैसे कि डिलीवरी [i] हमेशा पिकअप [i] के बाद होती है। चूंकि उत्तर बहुत बड़ा हो सकता है, हम इसे मॉड्यूलो 10^9 + 7 लौटा देंगे।

इसलिए, यदि इनपुट 2 की तरह है, तो आउटपुट 6 होगा, क्योंकि सभी संभावित ऑर्डर हैं (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2) , (P2,P1,D1,D2), (P2,P1,D2,D1) और (P2,D2,P1,D1)। और ऑर्डर (P1,D2,P2,D1) मान्य नहीं है क्योंकि पिकअप 2 डिलीवरी 2 के बाद है।

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

• मी :=1^9 + 7

• एन:=550

• आकार की एक सरणी dp परिभाषित करें:(N+5) x (N+5)। इसे -1 से भरें

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

  . लगेगा

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

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

  . लगेगा

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

• फ़ंक्शन को हल करें () को परिभाषित करें, यह पिकअप, लेफ्ट, i, j,

  में ले जाएगा

• अगर मैं 0 के समान है और j 0 के समान है, तो -

  • वापसी 1

• अगर dp[i, j] -1 के बराबर नहीं है, तो -

  • वापसी डीपी [i, जे]

• रिट:=0

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

  • रिट:=जोड़ें (रिट, एमयूएल (बाएं, हल करें (पिकअप + 1, बाएं -1, आई -1, जे)))

• अगर j> मैं, तो

  • रिट:=जोड़ें (रिट, एमयूएल (इनपिकअप, सॉल्व (इनपिकअप -1, लेफ्ट, आई, जे -1)))

• वापसी डीपी [i, जे] =सेवानिवृत्त

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

• वापसी हल (0, एन, एन, एन)

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
const int N = 550;
int dp[N + 5][N + 5];
lli add(lli a, lli b){
   return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
   return ((a % m) * (b % m)) % m;
}
class Solution {
   public:
   void pre(){
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
         }
      }
   }
   int solve(int inPickup, int left, int i, int j){
      if (i == 0 && j == 0)
      return 1;
      if (dp[i][j] != -1)
      return dp[i][j];
      int ret = 0;
      if (i > 0) {
         ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i
         - 1, j)));
      }
      if (j > i) {
         ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i,
         j - 1)));
      }
      return dp[i][j] = ret;
   }
   int countOrders(int n){
      pre();
      return solve(0, n, n, n);
   }
};
main(){
   Solution ob;
   cout << (ob.countOrders(2));
}

इनपुट

2

आउटपुट

6