不想说啥了…这是我被卡常数卡得最惨的一次…
首先根据期望的线性性,我们考虑每首歌能够被认出来的概率,也就是每首歌对答案贡献的期望.那么定义F[i]为第i首歌被认出来的概率是做不了的,自然想到F[i][j]表示第i首歌恰好在第j秒末被认出来的概率.那么暴力转移是O(n^3),过不了.(codeforces上有人说这个方法忽略小于精度要求的部分就跑过去了….一开始算着0.99^1000=4e-5没敢这么写…)
我们最后把所有F[i][j]加起来即可.(我一开始把所有可能成为最终局面的F[i][j]乘上i再乘上认出出第i+1首歌的概率再加起来….)
设认出第i首歌的概率是p[i],合唱开始的时刻是t[i]
则F[i][j]=p[i]*F[i-1][j-1]+(1-p[i])*p[i]*F[i-1][j-2]+(1-p[i])*(1-p[i])*p[i]*F[i-1][j-3]…….
F[i][j+1]=P[i]*F[i-1][j]+(1-p[i])*p[i]*F[i-1][j-1]+(1-p[i])*(1-p[i])*p[i]*F[i-1][j-2]…….
可见这个转移是很有规律的,我们可以从F[i][j]用O(1)的时间推出F[i][j+1],讨论j和t[i]的大小关系即可.这个转移是O(n^2)的,在较好的常数下可以通过.
最终能通过的代码如下.注释里有对卡常之处的说明.基本上是照着别人代码改的…Sky_miner说他没有被卡常....看来我代码太丑陋？
#include<cstdio>
#include<cmath>
double f[][];//roll arrays?
int main(){
int n,m;scanf("%d%d",&n,&m);
f[][]=;
double ans=;
int x,y;double p,g,h,l,tmp;
for(int i=;i<=n;++i){
f[i][]=;
for(int j=;j<i;++j)f[i][j]=;
scanf("%d%d",&x,&y);p=x/100.0;g=-p;h=pow(g,y-);l=h*g;
tmp=;
for(int j=i;j<=m;++j){
if(j<y){
tmp=tmp*g+p*f[i-][j-];//这几个地方如果不用一个tmp中转,直接写f[i][j]=…会T
}else if(j==y){
tmp=tmp*g+p*f[i-][j-]+f[i-][]*l;//同上
}else{
tmp=tmp*g-l*f[i-][j-y-]+l*f[i-][j-y]+p*f[i-][j-];//同上
}
f[i][j]=tmp;
ans+=f[i][j];
}
}
printf("%.7f\n",ans);
return ;
}