[SGU422]傻叉小明打字

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file sb_xiaoming.in Output file 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