计算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之后。

为了解决这个问题，我们将遵循以下步骤-

• m：= 1 ^ 9 + 7

• N：= 550

• 定义大小为（N + 5）x（N + 5）的数组dp。用-1填充

• 定义一个函数add()，这将需要a，b，

• return（（a mod m）+（b mod m））mod m

• 定义一个函数mul()，这将需要a，b，

• return（（a mod m）*（b mod m））mod m

• 定义一个函数solve()，这将需要inPickup，左，i，j，

• 如果i与0相同且j与0相同，则-

• 返回1

• 如果dp [i，j]不等于-1，则-

• 返回dp [i，j]

• ret：= 0

• 如果i> 0，则-

• ret：=添加（ret，mul（left，solve（inPickup + 1，left-1，i-1，j）））

• 如果j> i，则

• ret：=添加（ret，mul（inPickup，solve（inPickup-1，左，i，j-1）））

• return dp [i，j] = ret

• 从主要方法中执行以下操作-

• 返回solve(0,n,n,n)

让我们看下面的实现以更好地理解-

示例

#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