首页 > 代码库 > BZOJ2784[JLOI2012]时间流逝
BZOJ2784[JLOI2012]时间流逝
Description
生活可以很简单。可以探索水底世界的神秘，也可以去发现奇特新生物，亦或踏上一段新生的旅程。在必须要迎接挑战或跟周围的生物进行生存争夺之前，享受自由的飞翔。此时你会觉得生活是如此美好。
像蛇喜欢吃浮游生物一样（哦，我好像忘记告诉你这个常识），每天，你可以吃一些你周围的基础生物，然后会在你的尾巴上得到一个能量圈。你将会有好多种不同的能量圈，每一个都会被赋予一个能量。你可以拥有多个同种的能量圈，但是对于新得到的相同的能量圈，它的能量不能大于你已拥有的任何一个能量圈。除了前面的规则，获得新的能量圈的种类的概率是一样的。一天天过去，你得到越来越多的能量，开始了进化演变。
但是你也有自己的问题，有时你会面对邪恶的果冻鱼。它会追着你咬你，你不得不扔出最小能量值的能量圈然后赶忙逃跑。在这种情况下，你不会有任何的胃口了，因此这天你将不再得到任何能量圈。幸好，当你没有任何能量圈的时候，果冻鱼就算看见你也不会追着你，此时你可以好好地享用美食。
你听说当你的总的能量值超过了某个阈值之后，可以进化成强大模式并能够吃掉果冻鱼。是时候反击了！下面是本题的问题：预计要过多少天你才能进化成强大模式？（第一天默认你没有任何能量圈）
Input
输入包含多个测例。对每个测例会有两行。第一行是一个浮点数P，一个整数T和一个整数N。P是每天遇到果冻鱼的概率，T是阈值。第二行是N个不同的正整数，表示每一种能量圈的能量值。
Output
对于每个测例，输出一行表示预计要过多少天你的能量值能够超过阈值，四舍五入到三位小数。
Sample Input
0.5 0 1
1
0.5 1 2
1 2
1
0.5 1 2
1 2
Sample Output
1.000
2.000
2.000
HINT
对于所有数据，0.1≤P≤0.9，1≤T≤50，1≤N≤30。
题解：
概率DP题，我想了好久以后开始写，调了好几个小时都没有写对。
直到我看了czt的代码，我在发现我原本推出的状态转移方式是错误的。
正确的DP方式：用[i,j]记录已经筹集了i的能量，且拥有的最小能量圈为j，让其发展下去，直到筹集t以上的能量或失去j能量圈为止。
用f[i,j,1]记录有多大的几率是以失去j能量圈结束的，用f[i,j,2]记录结束的期望天数（结束包括以上两种方式)。
初始状态：f[i,j,1]=0，f[i,j,2]=1。（i>t）
假设[i,j]时获得了一个k的能量圈(k<=j)，则f[i,j]可以通过f[i+k,k]转移而来。
设x[k]为当前获得k的概率。
没有原地踏步的概率p2为(1-∑(f[i+k,k,2]*x[k]))。
不计原地踏步的情况（即获得k后进入[i+k,k]转态却以失去k结束），可以得出转到[i,k]状态的期望步数和tot为∑((f[i+k,k,2]+1)*x[k])。
推一推公式，可得f[i,j,1]=p/p2，f[i,j,2]=(tot/p2)+f[i,j,1]*1。
对于没有能量圈的状态（即答案），不会遇到鱼，转移方式与上面的略有不同，但大致是一样的。
代码：
1 var 2 i,j,k,l,n,m,t:longint; 3 p1,p2:extended; 4 b:array[0..1000,0..100,1..2]of extended; 5 lb,qz:array[0..100]of longint; 6 ans:extended; 7 begin 8 while not eof do 9 begin 10 fillchar(lb,sizeof(lb),0); 11 fillchar(qz,sizeof(qz),0); 12 fillchar(b,sizeof(b),0); 13 readln(p1,t,n); inc(t); p1:=1-p1; 14 for i:=1 to n do begin read(j); inc(lb[j]); end; readln; 15 for i:=1 to 100 do qz[i]:=qz[i-1]+lb[i]; 16 for i:=t-1 downto 1 do 17 for j:=1 to 100 do 18 if lb[j]>0 then 19 begin 20 p2:=1; 21 for k:=1 to j do 22 if lb[k]>0 then 23 begin 24 if i+k<t then 25 begin 26 p2:=p2-p1*(lb[k]/qz[j])*b[i+k,k,1]; 27 b[i,j,2]:=b[i,j,2]+p1*(lb[k]/qz[j])*(1+b[i+k,k,2]); 28 end else b[i,j,2]:=b[i,j,2]+p1*(lb[k]/qz[j]); 29 end; 30 b[i,j,1]:=(1-p1)/p2; b[i,j,2]:=b[i,j,2]/p2; 31 b[i,j,2]:=b[i,j,2]+b[i,j,1]; 32 end; 33 p2:=1; ans:=0; 34 for k:=1 to 100 do 35 if lb[k]>0 then 36 begin 37 if k<t then 38 begin 39 p2:=p2-(lb[k]/n)*b[k,k,1]; 40 ans:=ans+(lb[k]/n)*(1+b[k,k,2]); 41 end else ans:=ans+lb[k]/n; 42 end; 43 writeln((ans/p2):0:3); 44 end; 45 end.
BZOJ2784[JLOI2012]时间流逝
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。