记录编号	128275	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SGU U422]傻叉小明打字	最终得分	100
用户昵称	傻叉小明	是否通过	通过
代码语言	C++	运行时间	9.293 s
提交时间	2014-10-17 07:10:44	内存使用	69.48 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
const int MAXN=3000+10;
 
int N,T;
double p_error[MAXN]={0};
double p_no_error[MAXN][MAXN]={0};
 
double f_ex[MAXN]={0};
bool vis[MAXN]={false};
 
int len(int a,int b){
	if(a>b)return 0;
	return b-a+1;
}
 
double f1(int i){
	if(i>N)return 0;
	if(vis[i])return f_ex[i];
	double ex_v=1e10;
	int k;
	double now_ex_v=0;
	double tmp_p=0;
	for(k=i;k<=i;k++){
		now_ex_v=len(i,k)+T+len(i,k)*p_error[i];
		for(int j=i+1;j<=k;j++){
			now_ex_v+=p_no_error[i][j-1]*p_error[j]*(f1(j)+len(j,k));
		}
		now_ex_v+=p_no_error[i][k]*(f1(k+1));
		ex_v=min(now_ex_v,ex_v);
	}
	for(;k<=N;k++){
		now_ex_v+=1+p_error[i];
		now_ex_v+=p_no_error[i][k-1]*p_error[k]*(f1(k)+len(k,k));
		now_ex_v+=tmp_p;
		tmp_p+=p_no_error[i][k-1]*p_error[k];
		
		now_ex_v-=p_no_error[i][k-1]*(f1(k));
		now_ex_v+=p_no_error[i][k]*(f1(k+1));
		ex_v=min(now_ex_v,ex_v);
	}
	
	ex_v/=(1-p_error[i]);
	
	f_ex[i]=ex_v;
	vis[i]=true;
	return ex_v;
}
 
void init(){
	cin>>N>>T;
	for(int i=1;i<=N;i++){
		cin>>p_error[i];
	}
	for(int i=1;i<=N;i++){
		double now_p_no_error=1;
		for(int j=i;j<=N;j++){
			now_p_no_error*=(1-p_error[j]);
			p_no_error[i][j]=now_p_no_error;
		}
	}
}
 
void work(){
	printf("%.6lf\n",f1(1));
	//for(int i=1;i<=N;i++){
	//	printf("%.10lf\n",f1(i));
	//}
}
 
int main(){
	freopen("sb_xiaoming.in","r",stdin);
	freopen("sb_xiaoming.out","w",stdout);
	init();
	work();
	return 0;
}