数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中计算所有有效的取货和送货选项
假设我们有n个订单的列表，每个订单都有取货和送货服务。我们必须计算所有有效的取货/送货可能序列，使得delivery[i]总是在pickup[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 := 10^9 + 7
N := 550
定义一个大小为(N+5) x (N+5)的数组dp。用-1填充它。
定义一个函数add()，它将接收a, b，
返回((a mod m) + (b mod m)) mod m
定义一个函数mul()，它将接收a, b，
返回((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, left, i, j - 1)))
返回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
更新于：2020年6月8日
170 次浏览
广告