当前位置: 首页 > news >正文

桃城网站建设windows优化大师有毒吗

桃城网站建设,windows优化大师有毒吗,欧阳网站建设,北京数字智慧展厅设计装修服务商题目链接 Leetcode.1223 掷骰子模拟 Rating : 2008 题目描述 有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。 不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i](i 从 1…

题目链接

Leetcode.1223 掷骰子模拟 Rating : 2008

题目描述

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i](i 从 1 开始编号)。

现在,给你一个整数数组 rollMax和一个整数 n,请你来计算掷 n次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同,就认为这两个序列是不同的。由于答案可能很大,所以请返回 模 10^9 + 7之后的结果。

示例 1:

输入:n = 2, rollMax = [1,1,2,2,2,3]
输出:34
解释:我们掷 2 次骰子,如果没有约束的话,共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组,数字 1 和 2 最多连续出现一次,所以不会出现序列 (1,1) 和 (2,2)。因此,最终答案是 36-2 = 34。

示例 2:

输入:n = 2, rollMax = [1,1,1,1,1,1]
输出:30

示例 3:

输入:n = 3, rollMax = [1,1,1,2,2,3]
输出:181

提示:

  • 1<=n<=50001 <= n <= 50001<=n<=5000
  • rollMax.length==6rollMax.length == 6rollMax.length==6
  • 1<=rollMax[i]<=151 <= rollMax[i] <= 151<=rollMax[i]<=15

分析:

使用 动态规划 的方式求解。

我们定义 f(i,j,times)f(i,j,times)f(i,j,times) 为投掷了 i次骰子,并且第 i个骰子的点数是 j,且这个 j的连续出现次数是 times的不同序列数量。

按照定义,最终返回的结果为 f(n,1,1)+f(n,1,2)+...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1]+...f(n,6,rollMax[5])f(n,1,1) + f(n,1,2) + ...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1] + ...f(n,6,rollMax[5])f(n,1,1)+f(n,1,2)+...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1]+...f(n,6,rollMax[5])

∑j=16∑times=1rollMax[j−1]f(n,j,times)\sum_{j=1}^{6}\sum_{times=1}^{rollMax[j-1]}f(n,j,times)j=16times=1rollMax[j1]f(n,j,times)

状态转移:

  • 当 当前点k不等于 前一个点j时,f(i,k,1)=(f(i,k,1)+f(i−1,j,times))mod109+7f(i,k,1) = (f(i,k,1)+f(i-1,j,times)) mod 10^9+7f(i,k,1)=(f(i,k,1)+f(i1,j,times))mod109+7
  • 当 当前点k等于 前一个点j并且 times+1小于等于 rollMax[j-1]时,f(i,j,times+1)=(f(i,j,times+1)+f(i−1,j,times))mod109+7f(i,j,times+1) = (f(i,j,times+1) + f(i-1,j,times)) mod 10^9+7f(i,j,times+1)=(f(i,j,times+1)+f(i1,j,times))mod109+7

时间复杂度:O(n∗36∗15)O(n * 36 * 15)O(n3615)

C++代码:

const int MOD = 1e9+7;
using LL = long long;
class Solution {
public:int dieSimulator(int n, vector<int>& rollMax) {int f[n+1][7][16];memset(f,0,sizeof f);//初始化只投掷一次骰子的情况for(int i = 1;i <= 6;i++){f[1][i][1] = 1;}for(int i = 2;i <= n;i++){for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++){for(int k = 1;k <= 6;k++){if(j != k) f[i][k][1] = (f[i][k][1] + f[i-1][j][times])%MOD;else if(times + 1 <= rollMax[j - 1]){f[i][j][times+1] = (f[i][j][times+1] + f[i-1][j][times])%MOD;}}}}}LL ans = 0;//统计总的数量for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++) ans += f[n][j][times];}return ans % MOD;}
};

Java代码:

class Solution {private final int MOD = 1000_000_000+7;public int dieSimulator(int n, int[] rollMax) {int [][][] f = new int[n+1][7][16];for(int i = 1;i <= 6;i++){f[1][i][1] = 1;}for(int i = 2;i <= n;i++){for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++){for(int k = 1;k <= 6;k++){if(j != k) f[i][k][1] = (f[i][k][1] + f[i-1][j][times])%MOD;else if(times + 1 <= rollMax[j - 1]){f[i][j][times+1] = (f[i][j][times+1] + f[i-1][j][times])%MOD;}}}}}long ans = 0;for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++) ans += f[n][j][times];}return (int)(ans % MOD);}
}
http://www.ds6.com.cn/news/48206.html

相关文章:

  • 电商思维做招聘网站baidu 百度一下
  • 做网站最专业的公司有哪些老鬼seo
  • 做网站的原型文件下载百度入口网页版
  • 平湖手机网站建设百度手机快速排名点击软件
  • 2023石家庄疫情二次爆发福州seo排名优化公司
  • 属于教育主管部门建设的专题资源网站是网站权重等级
  • 基础网站建设代码上海网络推广公司
  • 优质的南昌网站建设亚马逊关键词搜索工具
  • 网站怎么做国际化怎么开网店新手入门
  • 今日新开传奇手游发布网58同城关键词怎么优化
  • 新乡网站建设产品推广文案100字
  • 如何加强政府门户网站维护和网站安全建设app注册推广平台
  • wordpress 段落显示不全优化工作流程
  • 做网站有一个火箭回顶部农村电商平台
  • 做网站一般用什么 语言seo石家庄
  • 连云港做网站哪里好长沙建站seo公司
  • 网站客服在线怎么做seo运营是做什么的
  • 毕业设计做网站还是系统好网页设计是干嘛的
  • 动态商务网站开发与管理关键词搜索查询
  • 网站建设请示手机百度搜索引擎入口
  • 网站建设mrd文档模板网上销售平台
  • 做后台财务系统网站最新时事热点
  • 南京做网站询南京乐识网站开发报价方案
  • 网上做网站赚钱吗seo网站优化优化排名
  • 猪八戒做网站要多少钱福州网络营销推广公司
  • 中信建设有限责任公司招聘深圳百度seo怎么做
  • 常州网站建设电话免费seo快速收录工具
  • 有哪些网站下载ppt是免费的关键词优化推广排名软件
  • seo网站排名推广央视新闻的新闻
  • 做技术开发的网站软文自助发稿平台oem