记录编号	456138	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SGU U422]傻叉小明打字	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.281 s
提交时间	2017-10-04 06:30:27	内存使用	0.28 MiB

#include <cstdio>
inline void m_min(double& x,double y){if(x>y) x=y;}
int n,T;
double P[3005],inv[3005],f[3005];
int solve()
{	freopen("sb_xiaoming.in","r",stdin);
	freopen("sb_xiaoming.out","w",stdout);
	scanf("%d%d",&n,&T);double t1,t2;
	for(int i=1;i<=n;++i) scanf("%lf",&P[i]),inv[i]=1-P[i];
	for(int i=n-1;i>=0;--i)
	{	t1=T+1+P[i+1]+inv[i+1]*f[i+1];t2=inv[i+1];
		f[i]=t1;
		for(int j=2,edg=n-i;j<=edg;++j)
		{	t2*=inv[i+j];
			t1+=2+t2*(f[i+j]-f[i+j-1]-1);
			m_min(f[i],t1);
		}
		f[i]/=inv[i+1];
	}
	printf("%.6lf",f[0]);
	return 0;
}
int Hard_problem=solve();
int main(){;}