本文共 1031 字，大约阅读时间需要 3 分钟。

题目链接：

题意：有n首曲子，一首一首的放给你听，然后要你猜歌名，对于第i首歌，你前ti-1秒每一秒猜对概率为pi，在第ti秒你必猜对，一旦第i首歌被猜对，立刻播放下一首，求T秒之后你猜对歌曲数量的期望

思路：dp[i][j]表示第i首歌刚好在第j秒时被猜对

有转移dp[i][j] = ∑(dp[i-1][j-k]*p[i]^(k-1)*(1-p[i])(1<=k<=t[i]-1))+dp[i-1][j-t[i]]*p[i]^(t[i]-1)

暴力转移复杂度O(nT²)，但求和部分可以前缀和优化，复杂度O(nT)

最后答案就是将所有的dp[i][j]加在一起，为什么是这样算的呢？因为你每转移一次就相当于多猜对一首歌，所以最后就是将所有的转移乘上发生这次转移的概率，即dp[i][j]

#include
   
    #include
    
     using namespace std;double p[5005], dp[5005][5005];int t[5005];double Pow(double x, int k){	double ans = 1;	while(k)	{		if(k%2)			ans = ans*x;		x = x*x;		k /= 2;	}	return ans;}int main(void){	double now, ans, temp;	int n, T, i, j, k;	scanf("%d%d", &n, &T);	for(i=1;i<=n;i++)	{		scanf("%lf%d", &p[i], &t[i]);		p[i] /= 100;	}	dp[0][0] = 1, ans = 0;	for(i=1;i<=n;i++)	{		now = 0;		temp = Pow(1-p[i], t[i]-1);		for(j=1;j<=T;j++)		{			now *= 1-p[i];			now += dp[i-1][j-1]*p[i];			if(j>=t[i])				now -= dp[i-1][j-t[i]]*temp*p[i];			dp[i][j] = now;			if(j>=t[i])				dp[i][j] += dp[i-1][j-t[i]]*temp;			ans += dp[i][j];		}	}	printf("%.10f\n", ans);	return 0;}
    
   

转载地址：http://pqmgf.baihongyu.com/