CF498B Name That Tune

$\color{deeppink}link$

令 $f_{i,j}$ 表示前 $i$ 个歌，已经听了 $j$ 秒的期望歌数。

有 $O(n^3)$ 的转移方程：

$f_{i,j}=\sum_{k=1}^{t_i} (1+f_{i-1,j-k})\times (1-p_i)^{k-1}\times p_i+f_{i-1,j-t_i}\times (1-p_i)^{t_i}$

观察这个方程，发现对于 $f_{i,j}$ 和 $f_{i,j-1}$ 的形式几乎一样，于是可以通过 $f_{i,j-1}$ 转移到 $f_{i,j}$。

$f_{i,j}=(f_{i,j-1}-f_{i-1,j-t_i-1}\times (1-p_i)^{t_i}-(1+f_{i-1,j-t_i-1})\times (1-p_i)^{t_i-1}\times p_i)\times (1-p_i)\\+(f_{i-1,j-1}+1)\times p_i$

复杂度是 $O(n^2)$。

#include<bits/stdc++.h>
#define now (i&1)
#define nxt (now^1)
#define db double
using namespace std;
const int N=5e3+50;

int n,T,t[N],s[N];
db p[N],f[2][N],ans;

main()
{
	cin>>n>>T;
	for(int i=1;i<=n;i++)cin>>p[i]>>t[i],p[i]/=100,s[i]=s[i-1]+t[i];
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		memset(f[now],0,sizeof f[now]);
		db pw=pow(1-p[i],t[i]-1);
		for(int j=i;j<=min(T,s[i]);j++)
		{
			if(j>t[i])
			{
				f[now][j]=(f[now][j-1]-
				f[nxt][j-t[i]-1]*pw*(1-p[i])-
				(f[nxt][j-t[i]-1])*pw*p[i])*(1-p[i])+
				(f[nxt][j-1])*p[i];
			}
			else
			{
				f[now][j]=f[now][j-1]*(1-p[i])+(f[nxt][j-1])*p[i];
			}
			if(j>=t[i])f[now][j]+=f[nxt][j-t[i]]*pw*(1-p[i]);
			ans+=f[now][j];
		}
	}
	cout<<fixed<<setprecision(10)<<ans;
}