[SGU422]傻叉小明打字

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 sb_xiaoming.in 输出文件 sb_xiaoming.out

【题目描述】

傻叉小明输入n(0<n<3000)个字符,第i个字符输入错的概率为pi(0<=pi<=0.5).任意时刻可以花费t时间来检查前面输入的文字有没有错误,如果有错误那么就需要按退格键不断从最后删除,直到没有错误的字符为止,然后再重新输入.输入一个字符\删除一个字符耗费时间为1,求出输入完全部的最小期望时间.


举例:有两个字符 第一个错误率为0,第二个错误率为0.5,t=1,那么最小期望时间的方案是先输入两个数,在检查是否前面输入的文字输入正确,如果不正确,删除直到剩下全部正确继续输入,如果依然不正确,删除继续输入,如果依然不正确,删除继续输入...  这样做期望时间为6.00000000000000


注意输出的时候保留6为小数,像这样:printf("%.6lf\n",ans);

【输入格式】

第一行2个整数:n,t

第二行n个实数:p1,p2,...,pn

【输出格式】

一个实数:最小期望

【样例输入】 


3 1
0.00001 0.5 0.00001

【样例输出】 

8.000080

【提示】

输出精度和原题不同(我不想写插件)

【来源】

sgu422