CF498B题解

咋黑色啊，这不是看到数据范围就去想 \(O(nT)\) 的做法吗？

然后仔细想想最靠谱的就是 DP。

设 \(dp[n][T]\) 表示听完第 \(n\) 首歌，总共听了 \(T\) 秒。

很明显有 \(dp[n][T]=dp[n-1][T-t_n] \times (1-p)^{t_n}+\sum_{i=1}^{t_n}dp[n-1][T-i] \times (1-p)^{i-1} \times p\)。

很明显这个是 \(O(nT^2)\) 的，接下来开始优化。

我们先先写成 \(dp[n][T]=\sum_{i=1}^{t_n}dp[n-1][T-i] \times (1-p)^{i-1}\)，最后令每一项乘上 \(p\)。

发现这个有点儿像把一个长度为 \(t_n\) 的区间当做一个多项式，翻转过来后带入 \(1-p\)，我们考虑每次平移一下这个多项式，再去掉多余的项。

然后你发现这个多项式带入后的值其实就是 \(dp[n][T-1]\)，所以并不需要新开一个变量。

预处理一下幂就可以做到 \(O(nT)\) 了。

答案为 \(\sum_{i=1}^n\sum_{j=1}^T dp[i][j]\)。

#include
#include
typedef long double db;
const int M=5005;
int n,m,t;double p,pw,ans,S[M],dp[2][M];
signed main(){
	int i,x;scanf("%d%d",&n,&m);dp[0][0]=1;
	for(int T=1;T<=n;++T){
		scanf("%d%d",&x,&t);p=.01*x;pw=pow(1-p,t);dp[T&1][0]=0;
		for(i=1;i<=m;++i)dp[T&1][i]=dp[T&1][i-1]*(1-p)+dp[T&1^1][i-1],i>t&&(dp[T&1][i]-=dp[T&1^1][i-t-1]*pw);
		for(i=1;i<=m;++i)dp[T&1][i]*=p,i>=t&&(dp[T&1][i]+=dp[T&1^1][i-t]*pw),ans+=dp[T&1][i];
	}
	printf("%.9lf",ans);
}