首页 > 其他分享 >筛子游戏

筛子游戏

时间:2022-12-30 19:45:15浏览次数:47  
标签:筛子 游戏 sum k3 k2 k1 dp

筛子游戏题解

题目大意:

吉吉国王正在玩一款手游,这个手游的规则非常简单。一开始你会得到三个筛子,三个筛子分别有\(k1, k2, k3\)面,也就是说分别可以扔出[1, k1], [1, k2], [1, k3]之间数。一开始的分数为\(0\),每次扔筛子都会扔出\(x, y, z\)三个数,但是这个游戏的特别之处在于每次开局都会给定三个数\(a, b, c\),如果满足\(x = a, y = b, z = c\),那么你的分数就会清零,否则你的分数就会加上\(x + y + z\)。现在吉吉国王想知道需要扔多少次才能使得他的分数大于\(n\)。

题目分析:

先令\(k = k1 + k2 + k3\),首先我们是可以预处理出来[3, K]每一步可能增加数值的概率,对于0情况特殊判断,我们假定dp[i]代表的含义为当前数值为i时,他还需要扔的期望数,使得他的分数大于n,从而我们可以推出一个状态转移方程$dp[i] = $$\sum$dp[i + k] * p[i + k] + \(dp[0] * p[0]\) + \(1\),而我们知道dp[0]是我们要求的答案,通过这个式子我们是无法直接得到答案的,所以我们令\(dp[i] = A[i] * dp[0] + B[i]\),将该式,带入进求和符号中的式子中,将有关\(dp[0]\)的部分,放在一起,可化简为,$dp[i] = $ (\(\sum\)A[i + k] * p[k] + \(p[0]\)) * \(dp[0]\) + \(\sum\)B[i + k] * p[k] + 1, 可以发现这和我们开始假定的式子很像,所以我们可以认为$A[i] = $$\sum$A[i + k] * p[k] + \(p[0]\), $B[i] = $ \(\sum\) B[i + k] * p[k] + 1. 而我们的答案$dp[0] = $ $B[0] / $$(1 - A[0])$.

代码:

#include<bits/stdc++.h>
using namespace std;
double dp[30004];
double A[30004];
double B[30004];
int main(){
	int n, k1, k2, k3, a, b, c;
	cin >> n >> k1 >> k2 >> k3 >> a >> b >> c;
	for (int i = 1; i <= k1; ++i){
		for (int j = 1; j <= k2; ++j){
			for (int k = 1; k <= k3; ++k3){
				if (i == a && j == b && k == c){
					dp[0]++;
				}else{
					dp[i + j + k] ++;
				}
			}
		}
	}
	int K = i + j + k;
	for (int i = 0; i <= K; ++i){
		dp[i] = dp[i] / (K * 1.0);
	}
	for (int i = n; i >= 0; --i){
		A[i] += dp[0];
		B[i] += 1;
		for (int j = 3; j <= K; ++j){
			if (i + j > n) continue;
			A[i] += A[i + j] * dp[j];
			B[i] += B[i + j] * dp[j];
		}
	}
	double ans = 0;
	ans = b[0] / (1 - A[0]);
	printf("%.6lf",ans);
}

标签:筛子,游戏,sum,k3,k2,k1,dp
From: https://www.cnblogs.com/zkhcwy/p/17015699.html

相关文章

  • 「博弈dp」棋盘游戏
    本题为12月30日22寒假集训每日一题题解题目来源:(未知)题面题目描述懒羊羊和小灰灰在玩一种棋盘游戏,棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角(1,m)放一枚硬......
  • 猜数字游戏
    voidmenu(){ printf("********************\n"); printf("***** 1.play *****\n"); printf("***** 0.exit *****\n"); printf("********************\n");}......
  • 纯JavaScript入门级小游戏:兔子抢金币(附演示地址+源码)
    Hello,大家好,我是兔哥,我又来分享好玩的入门级项目啦。今天给大家带来的是一个纯JavaScript入门级小游戏:兔子抢金币,规则非常简单,控制屏幕上的兔子去接天上掉下来的金币,接满20......
  • 辽阳盘锦游戏网站高防物理机租用
    针对流行的DDoS/CC流量型攻击,DDoS高防服务可以通过云端清洗集群、数据库监控牵引系统等技术进行有效的削弱。防止黑客的与同行的恶意攻击,一般比较吸金的行业基本上是每......
  • 辽阳盘锦游戏网站高防BGP物理机
    高防服务器是利用机房冗余带宽对机房服务器做了流量防护,可以抵御不同级别的网络攻击。在云计算时代,游戏、APP、金融、电商等有需求的业务可以通过接入DDoS高防服务......
  • 利用Python制作第一人称射击小游戏 含源代码
    大家好我是毕加锁(锁!)今天教大家利用Python制作第一人称小游戏 涉及知识点1.sprites2.pygame混音器3.图章  4.python基础语法.代码1发射声fromspritesimport*......
  • Ai实现FPS游戏自动瞄准 yolov5fps自瞄
    大家好我是毕加锁今天来分享一个Yolov5FPS跟枪的源码解析和原理讲解。代码比较粗糙各位有什么优化的方式可以留言指出,可以一起交流学习。 需要了解的东西和可能会遇到的......
  • 回归童年的美好 守住童年的回忆 那些年你玩过的游戏都有呢
    时过迁境,曾经与我们一同玩耍的发小、同学,也因为工作、家庭原因早已各奔东西不在自己的身边。还依稀记得孩童时期和小伙伴们一同蹲在大头电视前,快乐的玩着红白机的魂斗罗、......
  • 创建菜单与游戏界面
    本节课任务,实现游戏界面,页面导航栏先写前端在写后端。从上往下,减少代码重构导航栏专门拿出来,做组件前端的框架,模仿一遍格式:组件名称需要有两个大写字母bootstrap实现......
  • 【GDOI2017 Day 1 T2】取石子游戏
    Description如果你不想和题面软磨硬泡的话,请。。。。。(以下省略5000字)……给你一个1为根,N个点的树,每个点有权值。定义mex(S)表示不在S集合中最小的非负整数对于每个点,求......