首页 > 其他分享 >排队(利用step by step解题)(动态规划+概率)

排队(利用step by step解题)(动态规划+概率)

时间:2024-02-02 15:12:07浏览次数:26  
标签:p2 p1 1.0 排队 队伍 step 解题 概率 结账

第2题     排队(利用step by step解题) 查看测评数据信息

您刚刚在超市购物,然后前往结账。有两条队伍可用。第一个队伍目前有len1人,而第二个队伍有len2人。你想知道排在第一个队伍比排在第二条队伍“好”(即更早轮到你)的概率。第一个队伍的收银员准备开始给第一个队伍的第一个人结账。第二个队伍的收银员准备开始给第二个队伍的第一个人结账。结账的时间取决于收银员的经验。

对于每对正整数(p,k):具有经验p的收银员将花费k秒来对任何单个人结账的概率是:((1 / p)*(1 - 1 / p) ^(K-1))。第一个队伍的收银员的经验是p1,第二个队伍的收银员的经验p2。给出整数len1,len2,p1和p2。你想知道排在第一个队伍比排在第二条队伍“好”(即更早轮到你)的概率。更确切地说,计算当前站在第一个队伍中的最后一个人比第二个队伍中的最后一个人更早完成埋单的概率。

本题规定:0^0 = 1。

 

输入格式

 

多组测试数组。

 第一行,一个整数G。表示有G组测试数据。1 <= G <= 10。

 每组测试数据格式如下:

一行,len1,len2,p1,p2。  1 <= len1,len2,p1,p2 <= 1000。

 

 

输出格式

 

共G行,每行一个实数。误差不能超过0.000000001。

 

 

输入/输出例子1

输入:

10

1 2 2 1

 

1 3 3 7

 

3 1 7 3

 

12 34 56 78

 

3 6 8 4

 

739 472 691 138

 

604 259 303 513

 

167 303 405 276

 

677 533 589 380

 

289 491 826 606

 

 

输出:

0.5

0.9835390946502058

0.010973936899862834

0.999996203228025

0.5229465300297028

0.0

5.156019002856837E-6

0.9872711986032693

0.0

0.9986698635516139

 

 

样例解释

 

 

1.DP数组题目所求有一定联系(比如状态表示题目要求的答案,维度跟第几个,什么价值有一定关系)

2.循环从小到大还是从大到小取决于后一项跟前一项的关系,后一项跟前一项有关就是从小到大

以上总结可能不一定,先对dp有了一定初步的了解

看一下这句话“((1 / p)*(1 - 1 / p) ^(K-1))”,肯定是比较总要的,分析一下会发现,意思是,每一秒完成的概率都是1/p

 

 

发现这题的队伍长度,还是有一些关联的,考虑动态规划求解

f[len1][len2]表示A有len1,人,B有len2人,A比B好的概率

那么下一秒结账,A可能结账成功,B可能失败,记为X1;A可能成功,B可能成功,记为X2;A可能失败,B可能成功,记为X3;A可能失败,B可能失败,记为X4

分4种情况,根据“每一秒完成的概率都是1/p”,容易推出

X1=(1.0/p1)*(1.0-(1.0/p2))*f[i-1][j]    1/p1的概率,A成功;1-1/p2的概率,B成功;两概率相乘,A结账成功,队伍人数减少1人;B结账失败,队伍人数不边

X2=(1.0/p1)*(1.0/p2)*f[i-1][j-1];    1/p1的概率,A成功;1/p2的概率,B成功;两概率相乘,A结账成功,队伍人数减少1人;B结账成功,队伍人数减少1人

X3=(1.0-(1.0/p1))*(1.0/p2)*f[i][j-1]    1-1/p1的概率,A失败;1/p2的概率,B成功;两概率相乘,A结账失败,队伍人数不边;B结账成功,队伍人数减少1人

X4=(1.0-(1.0/p1))*(1.0-(1.0/p2))*f[i][j]    1-1/p1的概率,A失败;1-1/p2的概率,B失败;两概率相乘,A结账失败,队伍人数不边;B结账失败,队伍人数不边

边=>变,懒得改了,能看懂

然后四种情况相加,得

f[i][j]=X1+X2+X3+X4

可是X4包含f[i][j],不好求,移项

1-(   (1.0-(1.0/p1))*(1.0-(1.0/p2))    )  *f[i][j]=X1+X2+X3

于是推出了状态转移方程

外内循环都是从小到大,因为要先知道小的,才能知道大的,后一项跟前一项有关

 考虑一下答案,那肯定就是f[len1][len2]了

边界就是考虑len1=0,或者len2=0了

A走完,B不管有多少人,A都100%好

A不管有多少人,B走完,A都100%不好

A走完,B也走完,那无法确定A先走还是B先走,定为A,100%不好

 

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int g, c1, c2, p1, p2;
double f[N][N];
int main()
{
	scanf("%d", &g);
	while (g--)
	{
		memset(f, 0, sizeof f);
		
		scanf("%d%d%d%d", &c1, &c2, &p1, &p2);
		
//边界 for (int i=1; i<=c1; i++) f[i][0]=0; for (int i=1; i<=c2; i++) f[0][i]=1; f[0][0]=0; for (int i=1; i<=c1; i++) //队伍长度至少1,题目范围有说 for (int j=1; j<=c2; j++) {
//转移方程 double a=(1.0/p1)*(1.0/p2)*f[i-1][j-1]; double b=(1.0/p1)*(1.0-(1.0/p2))*f[i-1][j]; double c=(1.0-(1.0/p1))*(1.0/p2)*f[i][j-1]; double d=(1.0-(1.0/p1))*(1.0-(1.0/p2)); //注意没有*f[i][j]了 f[i][j]=(a+b+c)*1.0/(1.0-d); //转成除法 } printf("%.16lf\n", f[c1][c2]); } return 0; } /*
注释是错误,没改过来,别认真看。。。 1 1 1.0/p1*1.0/p2*f[i-1][j-1] 1 0 1.0/p1*(1.0-(1.0/p2))*f[i-1][j] 0 1 (1.0-(1.0/p1))*1.0/p2)*f[i][j-1] 0 0 (1.0-(1.0/p1))*(1.0-(1.0/p2))*f[i][j] */

 

 

ljx:

#include<bits/stdc++.h>
using namespace std;

int g;
double f[1005][1005],ans=0;//f[i][j]表示:l1有i个人 l2有j个人 ,A比B好的概率 
int main(){
    scanf("%d",&g);
    while(g--){
        int len1,len2,p1,p2;
        ans=0.0;
        scanf("%d%d%d%d",&len1,&len2,&p1,&p2);
        for(int i=1;i<=len2;i++) f[0][i]=1;
        for(int i=1;i<=len1;i++) f[i][0]=0;
        f[0][0]=0;
        for(int l1=1;l1<=len1;l1++){
            for(int l2=1;l2<=len2;l2++){
                double a=(1.0/p1*1.0)*(1.0-(1.0/p2*1.0))*f[l1-1][l2];//A 成功 B 不成功 
                double b=(1.0-(1.0/p1*1.0))*(1.0/p2*1.0)*f[l1][l2-1];//A 不成功 B 成功
                double c=(1.0/p1*1.0)*(1.0/p2*1.0)*f[l1-1][l2-1];//A 成功 B 成功
                double pro=(1.0-(1.0-(1.0/p1*1.0))*(1.0-(1.0/p2*1.0)));
                f[l1][l2]=(a+b+c)*1.0/pro*1.0;
            }
        }
        ans=f[len1][len2]*1.0;
        printf("%.16lf\n",ans);
    }   
    return 0;
}

 

       

标签:p2,p1,1.0,排队,队伍,step,解题,概率,结账
From: https://www.cnblogs.com/didiao233/p/18002897

相关文章

  • 洛谷题单指南-暴力枚举-P3654 First Step (ファーストステップ)
    原题链接:https://www.luogu.com.cn/problem/P3654题意解读:在r*c矩阵中,找连续k个.的总数。解题思路:本题直接枚举即可,在每一行中,以每一列为起点,连续判断k个元素,如果全为'.',则方案数加1在每一列中,以每一行为起点,连续判断k个元素,如果全为'.',则方案数加1注意:如果k=1,只有一个人......
  • QCN9024 QCN9074|Step by Step to load driver for DR9074-Triband on linux 5.17.0
    LoadingDR9074-TribandDriveronLinux5.17.0withATH11KSupportWallysrecentlyannouncedATH11KsupportforDR9074-TRIBANDonLinux,expandingitscompatibilitybeyondQualcommplatformstovariousLinuxembeddedsystems,includingUbuntu.Inthisartic......
  • abc337解题报告
    A略B略C略D略E略G简要题意这题比F简单很多,但是两题都不难。考虑枚举\(w\)的位置,把它拎起来当根,然后考虑一个儿子\(son\)认为\(u\)在它的子树内。实际上,我们不可能把\(w\)拎起来当根,所以我们对\(son\)分两类讨论:\(son\)是\(w\)的儿子,我们求出\(v\)......
  • abc338解题报告
    A略B略C略D简要题意思路点拨考虑对于相邻的两个需要旅行的元素\((u,v)\),我们认为\(u<v\)。如果一个桥的左端点在\(u\)到\(v-1\)之间,需要\(n-v+u\)的代价。反之只需要\(v-u\)的代价。使用差分数组维护即可。E简要题意思路点拨对于一条边\(u,v\)认为\(......
  • NOI 2017 蚯蚓排队 题解
    Meaning给定一些数字,对它们进行首尾相接和断开两种操作。对于每次询问,求对于每个数字,其后长度一定的数字串在给定数字串中出现的次数,并给出这些次数之积。Soultion对于每次首尾相接或断开的操作,如果直接对断点或合点两侧的整个数字串进行操作,时间复杂度不可接受。由于每次查询......
  • 请教问题,layui step 这个分步表单的高度怎么自适应
    ​​这里设置height:auto是不显示的  指定高度是可以显示的这是那个步骤条配置`//步骤条配置layui.config({base:'./step-lay/'}).use(['form','step'],function(){var$=layui.$,form=layui.form,st......
  • 中考英语连词成句解题技巧讲解
    一、命题趋势连词成句是中考英语试题中新设的考查项目。这样,写作实际上分成了三个层次:1)词语的运用。是在命题人规定好的框架内,根据特定的语境,依据基本的规则完成单句。这如同体育竞技中的完成规定动作;2)连词成句。这个环节属于半开放式的表达形式。词汇范围有限定,但组合形式不......
  • 《SAIS Supervising and Augmenting Intermediate Steps for Document-Level Relation
    代码 原文地址 预备知识:1.什么是标记索引(tokenindices)?标记索引是一种用于表示文本中的单词或符号的数字编码。它们可以帮助计算机理解和处理自然语言。例如,假如有一个字典{"我":1,"是":2,"Bing":3,".":4},那么文本"我是Bing."的标记索引就是[1,2,3,4]。不同的模......
  • 栈与队列解题报告
    刚考完试。重返oi!这次挂掉80pts20pts挂在T1,未考虑读的时候数字占多个字符,60pts挂在多测未清空上。T1https://www.luogu.com.cn/problem/P1981经典表达式求值。我这里采用了一种比较奇特的方法。我以每个加号为分界线。当我遍历到其中一个加号时,保证加号之前只有一个数。然......
  • 集训队论文浅读 - 信息学竞赛中构造题的常用解题方法
    抽屉原理把\(n\)个物品放入\(k\)个抽屉中,其中至少有一个抽屉中有\(\lceil\dfrac{n}{k}\rceil\)个物品,并一定有一个抽屉包含\(\lfloor\dfrac{n}{k}\rfloor\)个物品。构造题中考虑构造不同情况的抽屉,应对构造权值类问题。对于取整符号要敏感。Codeforces1450C2构......