C++의 모든 유효한 픽업 및 배송 옵션 계산

<시간/>

n개의 주문 목록이 있다고 가정하고 각 주문에는 픽업 및 배달 서비스가 있습니다. 우리는 delivery[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). 그리고 Pickup 2가 Delivery 2 이후이기 때문에 주문(P1,D2,P2,D1)은 유효하지 않습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=1^9 + 7
N :=550
(N+5) x (N+5) 크기의 배열 dp를 정의합니다. 이것을 -1로 채우십시오.
add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m)) mod m
solve() 함수를 정의하면 inPickup, left, i, j,
가 사용됩니다.
i가 0과 같고 j가 0과 같으면 -
- 1 반환
dp[i, j]가 -1과 같지 않으면 -
- 반환 dp[i, j]
ret :=0
i> 0이면 -
- ret :=add(ret, mul(left, solve(inPickup + 1, left - 1, i - 1, j)))
j> i이면
- ret :=add(ret, mul(inPickup, solve(inPickup - 1, 왼쪽, i, j - 1)))
반환 dp[i, j] =ret
주요 방법에서 다음을 수행하십시오 -
해결(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));
}