计算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