记录编号	455891	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	1667.[SGU U422]傻叉小明打字	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	3.244 s
提交时间	2017-10-03 13:43:43	内存使用	0.30 MiB

#include <cstdio>
template<typename T>inline void m_min(T& x,T 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]);
	for(int i=1;i<=n;++i)
	{	inv[0]=1;f[i]=1e16;
		for(int j=1;j<=i;++j) inv[j]=inv[j-1]*(1-P[n-i+j]);
		t1=inv[1]*f[i-1];t2=1-inv[1];
		for(int j=1;j<=i;++j)
		{	m_min(f[i],(T+t1+j+t2)/inv[1]);
			t1+=inv[j+1]*(f[i-j-1]-f[i-j]);
			t2+=1-inv[j+1];
		}
	}
	printf("%.6lf",f[n]);
	return 0;
}
int Hard_problem=solve();
int main(){;}