codeforces 498 B. Name That Tune（概率期望dp）

题目链接

题目描述：
识别歌曲，每一秒钟你有 pi $p_i$的概率猜出这首歌的名字
如果听到 ti $t_i$秒，就一定能猜出这首歌
求T秒内能识别出的歌的曲目期望
如果识别所有歌曲的时间都比T秒快，则在识别出最后一首歌曲后停止游戏

分析：
一个比较显然的dp
f[i][j] $f[i][j]$表示前 i $i$首歌，在第 j $j$秒的时候认出

f[i][j]<−∑t[i]−1k=1f[i−1][j−k]∗p[i](1−p[i])k−1 $f[i][j]<-\underset{k=1}{\overset{t[i]-1}{\sum }}f[i-1][j-k]\ast p[i](1-p[i]{)}^{k-1}$

f[i][j]<−f[i−1][j−t[i]]∗(1−p[i])t[i] $f[i][j]<-f[i-1][j-t[i]]\ast (1-p[i]{)}^{t[i]}$

f[i][j]=∑t[i]−1k=1f[i−1][j−k]∗p[i](1−p[i])k−1+f[i−1][j−t[i]]∗(1−p[i])t[i] $f[i][j]=\underset{k=1}{\overset{t[i]-1}{\sum }}f[i-1][j-k]\ast p[i](1-p[i]{)}^{k-1}+f[i-1][j-t[i]]\ast (1-p[i]{)}^{t[i]}$

这样转移的复杂度是 O(nT2) $O(n{T}^2)$，有点不科学

仔细观察一下：
f[i][j]=∑t[i]−1k=1f[i−1][j−k]∗p[i](1−p[i])k−1+f[i−1][j−t[i]]∗(1−p[i])t[i] $f[i][j]=\underset{k=1}{\overset{t[i]-1}{\sum }}f[i-1][j-k]\ast p[i](1-p[i]{)}^{k-1}+f[i-1][j-t[i]]\ast (1-p[i]{)}^{t[i]}$

f[i][j+1]=∑t[i]−1k=1f[i−1][j+1−k]∗p[i](1−p[i])k−1+f[i−1][j+1−t[i]]∗(1−p[i])t[i] $f[i][j+1]=\underset{k=1}{\overset{t[i]-1}{\sum }}f[i-1][j+1-k]\ast p[i](1-p[i]{)}^{k-1}+f[i-1][j+1-t[i]]\ast (1-p[i]{)}^{t[i]}$

=∑t[i]−1k=1f[i−1][j−k]∗p[i](1−p[i])k−1−f[i−1][j−t[i]]∗p[i](1−p[i])t[i]−2+f[i−1][j+1−t[i]]∗(1−p[i])t[i] $=\underset{k=1}{\overset{t[i]-1}{\sum }}f[i-1][j-k]\ast p[i](1-p[i]{)}^{k-1}-f[i-1][j-t[i]]\ast p[i](1-p[i]{)}^{t[i]-2}+f[i-1][j+1-t[i]]\ast (1-p[i]{)}^{t[i]}$

=f[i][j]−f[i−1][j−t[i]]∗p[i](1−p[i])t[i]−2+f[i−1][j+1−t[i]]∗(1−p[i])t[i]−f[i−1][j−t[i]]∗(1−p[i])t[i] $=f[i][j]-f[i-1][j-t[i]]\ast p[i](1-p[i]{)}^{t[i]-2}+f[i-1][j+1-t[i]]\ast (1-p[i]{)}^{t[i]}-f[i-1][j-t[i]]\ast (1-p[i]{)}^{t[i]}$

#include<cstring>
#include<cstdio>
#include<iostream>

using namespace std;

int n,T,t[5002];
double p[5002],f[5002][5002];

double KSM(double a,int p) {
if (p<0) return 0;
double t=1;
while (p) {
if (p&1) t=t*a;
        a=a*a;
        p>>=1;
    }
return t;
}

int main() {
scanf("%d%d",&n,&T);
for (int i=1;i<=n;i++) {
scanf("%lf%d",&p[i],&t[i]);
        p[i]/=100.0;
    }
double ans=0;
    f[0][0]=1.0;
for (int i=0;i<=n;i++) {
double p1,p2;
if (i>0&&t[i]>2) p1=KSM(1-p[i],t[i]-2);
        p2=KSM(1-p[i+1],t[i+1]-1);
for (int j=0;j<=T;j++) {
if (f[i][j]==0) continue;
if (i>0&&t[i]>2) {
double tmp=f[i][j];
if (j>=t[i]) tmp-=f[i-1][j-t[i]]*p1*(1-p[i]);
if (j>=t[i]-1) tmp-=f[i-1][j-t[i]+1]*p1*p[i];
                f[i][j+1]+=tmp*(1-p[i]);
            }
if (j+1<=T&&t[i+1]>1) f[i+1][j+1]+=f[i][j]*p[i+1];
if (j+t[i+1]<=T) f[i+1][j+t[i+1]]+=f[i][j]*p2;
if (i>0) ans+=f[i][j];
        }
    }
printf("%0.7lf\n",ans);
return 0;
}