C ++中的骰子滚动模拟

  • Z时代
  • 2024-01-10
  • 分类：综合

假设骰子模拟器为每个卷生成一个1到6的随机数。我们要向生成器引入一个约束，以使其不能连续滚动i的次数不超过rollMax [i]（1索引）。假设我们有一个整数数组rollMax和一个整数n，我们必须返回可以用精确的n个roll获得的不同序列的数量。如果至少一个元素彼此不同，则认为这两个序列不同。因此，如果n为2，则rollMax = [1,1,2,2,2,3]，则输出为34。因此，如果没有约束，则在骰子上将有2个骰子，在骰子上有6 * 6 = 36个可能的组合，在这种情况下，数字1和2最多连续出现一次，因此序列(1,1)和(2,2)不会出现。因此最终答案将是36 – 2 = 34。

为了解决这个问题，我们将遵循以下步骤-

  • 创建一个名为的方法dfs()，它将使用dieLeft，last，currLen，数组r和矩阵dp

  • 如果dieLeft = 0，则返回1

  • 如果dp [dieLeft] [last] [currLen]不为-1，则返回dp [dieLeft，last，currLen]

  • 计数器：= 0

  • 对于0到6的i

    • 如果i =最后并且r [i] = currLen，则跳过下一部分并进行下一次迭代

    • 计数器：= dfs（dieLeft – 1，i，当i = last时为currLen + 1，否则为1，r，dp）

  • dp [dieLeft，last，currLen]：=计数器

  • return dp [dieLeft，last，currLeft]

  • 主要方法将是-

  • 创建一个称为dp的3d数组，其阶数为（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

以上是 C ++中的骰子滚动模拟 的全部内容， 来源链接： utcz.com/z/326441.html

回到顶部