假设我们有一个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