ধরুন আমাদের কাছে n অর্ডারের একটি তালিকা আছে, প্রতিটি অর্ডারে পিকআপ এবং ডেলিভারি পরিষেবা রয়েছে। আমাদের সমস্ত বৈধ পিকআপ/ডেলিভারির সম্ভাব্য ক্রম গণনা করতে হবে যেমন ডেলিভারি[i] সর্বদা পিকআপের পরে হয়। যেহেতু উত্তরটি অনেক বড় হতে পারে, আমরা এটিকে মডিউল 10^9 + 7 ফেরত দেব।
সুতরাং, যদি ইনপুটটি 2 এর মত হয়, তাহলে আউটপুট হবে 6, কারণ সমস্ত সম্ভাব্য অর্ডারগুলি হল (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 এর পরে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
মি :=1^9 + 7
-
N :=550
-
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:(N+5) x (N+5)। -1
দিয়ে এটি পূরণ করুন -
একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
ফিরুন ((a mod m) + (b mod m)) mod m
-
একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
(a mod m) * (b mod m)) mod m
ফেরত দিন -
একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি পিকআপ, বাম, আই, জে,
গ্রহণ করবে -
যদি 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
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
রিটার্ন সমাধান (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
