สมมติว่าเครื่องจำลองการตายสร้างตัวเลขสุ่มตั้งแต่ 1 ถึง 6 สำหรับแต่ละม้วน เราต้องการแนะนำข้อ จำกัด ให้กับตัวสร้างเพื่อไม่ให้หมุนหมายเลข i มากกว่า rollMax[i] (1-indexed) ติดต่อกัน พิจารณาว่าเรามีอาร์เรย์ของจำนวนเต็ม rollMax และจำนวนเต็ม n เราต้องคืนค่าจำนวนลำดับที่แตกต่างกันที่สามารถรับได้ด้วย n ม้วนที่แน่นอน ทั้งสองลำดับจะถือว่าแตกต่างกันหากองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบแตกต่างกัน ดังนั้นถ้า n เป็น 2 แล้ว rollMax =[1,1,2,2,2,3] ผลลัพธ์จะเป็น 34 ดังนั้นจะมี 2 ม้วนบนแม่พิมพ์ หากไม่มีข้อจำกัด บนแม่พิมพ์จะมี 6*6 =36 ชุดค่าผสมที่เป็นไปได้ ในกรณีนี้ หมายเลข 1 และ 2 ปรากฏอย่างมากที่สุด 1 ครั้งติดต่อกัน ดังนั้นลำดับ (1,1) และ (2,2) จะไม่เกิดขึ้น ดังนั้นคำตอบสุดท้ายจะเป็น 36 – 2 =34
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างหนึ่งวิธีที่เรียกว่า dfs() ซึ่งจะใช้ dieLeft, last, currLen, array r และ matrix dp
- ถ้า dieLeft =0 ให้คืนค่า 1
- ถ้า dp[dieLeft][last][currLen] ไม่ใช่ -1 ให้คืนค่า dp[dieLeft, last, currLen]
- ตัวนับ :=0
- สำหรับ i ในช่วง 0 ถึง 6
- ถ้า i =สุดท้าย และ r[i] =currLen ให้ข้ามส่วนถัดไปและทำซ้ำต่อไป
- ตัวนับ :=dfs(dieLeft – 1, i, currLen + 1 เมื่อ i =สุดท้าย มิฉะนั้น 1, r, dp)
- dp[dieLeft, last, currLen] :=ตัวนับ
- ส่งคืน dp[dieLeft, สุดท้าย, currLeft]
- วิธีหลักจะเป็นเช่น −
- สร้างอาร์เรย์ 3 มิติที่เรียกว่า dp of order (n + 1) x 6 x 16 แล้วเติมด้วย -1
- ส่งคืน dfs(n, 0, 0, rollMax, dp)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
2 [1,1,2,2,2,3]
ผลลัพธ์
34
