计算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（（amodm）+（bmodm））modm
定义一个函数mul()，这将需要a，b，
return（（amodm）*（bmodm））modm
定义一个函数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）））
returndp[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