本文共 1552 字，大约阅读时间需要 5 分钟。

首先因为这个能记住前$k$条路很不好搞

因为$dp$过程中无法知道它记住的是那些门

所以就需要把门抽象成两类

一种是进去后回到起点,花费总时间$va{l}_1$,有$s_1$扇门

一种是进去后就能逃生,花费总时间$va{l}_2$,有$s_2$扇门

这样把所有第一类门权值看作$\frac{va{l}_1}{s_1}$,把所有第二类门看作$\frac{va{l}_2}{s_2}$

因为对于同一类门来说,被选到的概率均等,造成的影响相同,所以可以用期望代替

这样我们就可以不去关心目前记住的是那些门,只需要知道记住了多少门就行!!

设$f[i]$为记住了$i$扇门,逃生还需花费的时间

先对$k$处理一下,$k=min(k,s_1)$

那么终止点就是$$f[k]=(f[k]+va{l}_1)\ast p_1+va{l}_2\ast p_2$$

其中$p_1=\frac{s_1-k}{n-k}$表示此时去第一类门

其中$p_2=\frac{s_2}{n-k}$,表示去第二类门

然后一般情况递推式是$$f[i]=(f[i+1]+va{l}_1)\ast \frac{s_1-i}{n-i}+va{l}_2\ast \frac{s_2}{n-i}$$

$f[0]$就是答案

#include 
   
    using namespace std;int n,k;double f[109];int main(){
   	int t,casenum=0; cin >> t;	while( t-- )	{
   		cin >> n >> k;		double val1=0,val2=0,s1=0,s2=0;		for(int i=1;i<=n;i++)		{
   			double x; cin >> x;			if( x<0 )	val1 -= x,s1++;			else	val2 += x,s2++;		}		if( s2==0 )			{
   			printf("Case %d: -1\n",++casenum);			continue;		}		if( s1>0.0 )val1 /= s1;		if( s2>0.0 )val2 /= s2;		k = min( k,(int)s1 );		double p1 = (s1-k)/(n-k), p2 = s2/(n-k);		f[k] = val1*p1+val2*p2;		f[k] /= (1.0-p1);		for(int i=k-1;i>=0;i--)		{
   			p1 = (s1-i)/(n-i), p2 = s2/(n-i);			f[i] = ( f[i+1]+val1 )*p1+val2*p2;		}		printf("Case %d: %.7lf\n",++casenum,f[0] );	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109350787 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！