Đếm tất cả các tùy chọn nhận và giao hàng hợp lệ trong C ++

Giả sử chúng ta có một danh sách gồm n đơn hàng, trong mỗi đơn hàng đều có dịch vụ nhận hàng và giao hàng. Chúng tôi phải tính tất cả các trình tự nhận / giao hợp lệ có thể xảy ra sao cho việc giao hàng [i] luôn sau khi nhận hàng [i]. Vì câu trả lời có thể rất lớn, chúng tôi sẽ trả về nó theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là 2, thì đầu ra sẽ là 6, vì Tất cả các lệnh có thể là (P1, P2, D1, D2), (P1, P2, D2, D1), (P1, D1, P2, D2) , (P2, P1, D1, D2), (P2, P1, D2, D1) và (P2, D2, P1, D1). Và đơn đặt hàng (P1, D2, P2, D1) không hợp lệ vì Nhận hàng 2 là sau Giao hàng 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=1 ^ 9 + 7

• N:=550

• Xác định một mảng dp có kích thước:(N + 5) x (N + 5). Điền vào điều này với -1

• Xác định một hàm add (), điều này sẽ lấy a, b,

• return ((a mod m) + (b mod m)) mod m

• Xác định một hàm mul (), điều này sẽ nhận a, b,

• return ((a mod m) * (b mod m)) mod m

• Xác định một hàm giải quyết (), điều này sẽ lấy inPickup, left, i, j,

• nếu tôi giống 0 và j giống 0, thì -

  • trả lại 1

• nếu dp [i, j] không bằng -1 thì -

  • trả về dp [i, j]

• ret:=0

• nếu tôi> 0, thì -

  • ret:=add (ret, mul (left, giải (inPickup + 1, left - 1, i - 1, j)))

• nếu j> i, thì

  • ret:=add (ret, mul (inPickup, giải quyết (inPickup - 1, left, i, j - 1)))

• return dp [i, j] =ret

• Từ phương thức chính, thực hiện như sau -

• trả về giải quyết (0, n, n, n)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

2

Đầu ra

6