ধরুন আমাদের কাছে 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