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

这个二分我是真想不到,令人窒息的操作…

定义$f[i][j]$表示从第$i$关开始一直通关到最后,已经花了$j$个罚时,还能打破记录的最小期望时间

首先加上第$i$关成功了条件下的期望值,毫无疑问$f[i][j]+=p_i\ast (f[i+1][j]+t_{i+1}-t_i)$即可

如果第$i$关失败

那么当$j+d_i<=r-n-1$时,既可以重新开始,也可以硬着吃下$d_i$的罚时

$$f[i][j]+=(1-p_i)\ast \min (d_i+t_{i+1}-t_i+f[i+1][j+d_i],f[0][0])$$

否则,如果硬吃罚时无法破纪录,只能重开

$$f[i][j]+=(1-p_i)\ast f[0][0]$$

然后$f[0][0]$你不知道…

令人窒息的操作出现了,我们可以二分$f[0][0]$,设二分值为$mid$

把$mid$带进去求出算出来的$f[0][0]$

若$mid<f[0][0]$,说明$mid$需要变小,否则,$mid$需要变大

为什么能二分我也不知道

#include 
   
    using namespace std;#define double long doubleconst int maxn = 5009;const double eps = 1e-8;int n,r,m,d[maxn],t[maxn];double p[maxn],f[109][maxn];//f[i][j]表示[i,m]已经用了j的惩时,破纪录还需要的时间 double isok(double x){
   	for(int i=0;i<=m;i++)	for(int j=0;j<=r-n-1;j++)		f[i][j] = 0;	for(int i=m-1;i>=0;i--)	for(int j=0;j<=r-n-1;j++)	{
   		f[i][j] = p[i]*( f[i+1][j]+t[i+1]-t[i] );//成功 		if( j+d[i]<=r-n-1 )//重开或者吃惩时			f[i][j] += (1.0-p[i] )*min( x,f[i+1][j+d[i]]+d[i]+t[i+1]-t[i] );		else//只能重开 			f[i][j] += ( 1.0-p[i] )*x;			 	}	return f[0][0];}int main(){
   	cin >> n >> r >> m;	for(int i=1;i<=m;i++)	cin >> t[i] >> p[i] >> d[i];	++m; t[m] = n, p[m] = 1.0, d[m] = 0;	t[0] = 0, p[0] = 1.0, d[0] = 0;	double l = 0, r = 1e17 , ans = 0;	while( fabs(r-l)>=eps )	{
   		double mid = ( l+r )/2.0;		if( isok(mid)>=mid )	l = mid+eps;//mid比较小 		else	r = mid-eps, ans = mid;//mid比较大 	}	printf("%.9Lf",ans );}
   

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