นับตัวเลือกการรับและการจัดส่งที่ถูกต้องทั้งหมดใน 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) ไม่ถูกต้องเนื่องจาก Pickup 2 อยู่หลังการส่งมอบ 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=1^9 + 7

• ไม่มี :=550

• กำหนดขนาดอาร์เรย์ dp:(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

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้เวลา inPickup, left, i, j,

• ถ้าฉันเหมือนกับ 0 และ j เหมือนกับ 0 แล้ว −

  • กลับ 1

• ถ้า dp[i, j] ไม่เท่ากับ -1 แล้ว −

  • กลับ dp[i, j]

• ยกเลิก :=0

• ถ้า i> 0 แล้ว −

  • ret :=add(ret, mul(left, dissolve(inPickup + 1, left - 1, i - 1, j)))

• ถ้า j> i แล้ว

  • ret :=add(ret, mul(inPickup, dissolve(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