Mô phỏng cuộn xúc xắc trong C ++

Giả sử một bộ mô phỏng khuôn tạo ra một số ngẫu nhiên từ 1 đến 6 cho mỗi cuộn. Chúng tôi muốn giới thiệu một ràng buộc cho trình tạo sao cho nó không thể cuộn số i nhiều hơn rollMax [i] (1-indexed) lần liên tiếp. Hãy xem xét chúng ta có một mảng các số nguyên rollMax và một số nguyên n, chúng ta phải trả về số dãy riêng biệt có thể thu được với n cuộn chính xác. Hai trình tự được coi là khác nhau nếu có ít nhất một phần tử khác nhau. Vì vậy, nếu n là 2, sau đó rollMax =[1,1,2,2,2,3], thì đầu ra sẽ là 34. Vì vậy, sẽ có 2 cuộn trên khuôn, nếu không có ràng buộc, trên khuôn có 6 * 6 =36 kết hợp có thể có, trong trường hợp này các số 1 và 2 xuất hiện nhiều nhất một lần liên tiếp, do đó chuỗi (1,1) và (2,2) không thể xảy ra. vì vậy câu trả lời cuối cùng sẽ là 36 - 2 =34.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

tạo một phương thức gọi là dfs (), phương thức này sẽ lấy dieLeft, last, currLen, mảng r và ma trận dp
nếu dieLeft =0, thì trả về 1
nếu dp [dieLeft] [last] [currLen] không phải là -1, thì trả về dp [dieLeft, last, currLen]
bộ đếm:=0
cho tôi trong phạm vi từ 0 đến 6
- nếu i =last và r [i] =currLen, thì hãy bỏ qua phần tiếp theo và chuyển sang lần lặp tiếp theo
- counter:=dfs (dieLeft - 1, i, currLen + 1 khi i =last, nếu không thì 1, r, dp)
dp [dieLeft, last, currLen]:=counter
return dp [dieLeft, last, currLeft]
phương thức chính sẽ giống như -
tạo một mảng 3D được gọi là dp có thứ tự (n + 1) x 6 x 16 và điền vào mảng này với -1
trả về dfs (n, 0, 0, rollMax, dp)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
class Solution {
   public:
   int dfs(int dieLeft, int last, int currLen, vector <int> &r,vector < vector < vector <int> > > &dp){
      if(dieLeft == 0){
         return 1;
      }
      if(dp[dieLeft][last][currLen]!=-1)return dp[dieLeft][last][currLen];
      int counter = 0;
      for(int i =0;i<6;i++){
         if(i==last && r[i] == currLen)continue;
         counter = (counter%mod + (dfs(dieLeft-1,i,i==last?currLen+1:1,r,dp))%mod)%mod;
      }
      dp[dieLeft][last][currLen] = counter%mod;
      return dp[dieLeft][last][currLen]%mod;
   }
   int dieSimulator(int n, vector<int>& rollMax) {
      vector < vector < vector <int> > > dp(n+1, vector < vector <int> > (6, vector <int>(16, -1)));
      return dfs(n,0,0,rollMax, dp)%mod;
   }
};
main(){
   vector<int> v = {1,1,2,2,2,3};
   Solution ob;
   cout << (ob.dieSimulator(2,v));
}

Đầu vào

2
[1,1,2,2,2,3]

Mô phỏng cuộn xúc xắc trong C ++

Ví dụ

Đầu vào

Đầu ra