首页 > 代码库 > codeforces284 div1 B:概率dp

codeforces284 div1 B:概率dp

蛋疼的期末。。好久没有A题了,,惭愧啊

昨晚打起精神准备做cf 结果竟然忘记注册了。。拿学长号看了看题,今早起来补了一道dp

题目大意:

有n首歌,你需要边听边猜

对于第 i 首歌 每听一分钟你猜出它的概率为p[i],同时在听这个歌t[i] 分钟时,你一定能猜出来

猜完当前歌曲 下一分钟开始听下一首歌

给定总时间 T 求猜出歌曲的期望。。

 

题解:
这个题的算法我想的还是很快的

开两个数组

dp[i][j]表示第 i 分钟还在听第 j 首歌的概率,这样如果没有 t[i]的限制就可以很容易的写出dp方程了,

加上t[i]以后怎么做呢,我的做法是再维护一个数组

q[i][j]表示在第 i 分钟将要开始听第 j 首歌的概率

显然在 i 时间 听 j 歌曲的 第 t[i] 分钟的概率即为 q[i-t[i]] * (1-p[j])^(t[i]-1) (前t[i]-1分钟都没有猜出来)

由于概率是线性叠加起来的。所以在转移的时候直接把这一部分单独考虑就可以了

 

吐槽:

我爆了一次内存,然后换成滚动数组过了。。。听说某金牌爷比赛最后一刻写完 爆内存改完没来得及交

904ms飘过。。。听说一堆红名爷、final爷tle了,果然上天有时候还是会稍微眷顾一下弱逼的

比赛的时候过了这题竟然可以黄。。。早知道就用学长的号交一发了。。

 

代码:

#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>#include<math.h>#include<queue>using namespace std;#define MAXN 10000const double eps=0.0000000000000001;double dp[2][5010];double p[5010];long long t[5010];double q[5010][5010];int main(){    long long n,k;    cin>>n>>k;    for(int i=0;i<n;i++)    {        cin>>p[i]>>t[i];        p[i]/=100;    }    dp[0][0]=1;    q[0][0]=1;    for(int i=1;i<=k;i++)    {        for(int j=0;j<n;j++)        {            if(dp[(i-1)%2][j]<eps)                continue;            double tmp;            if(i>=t[j])            {                tmp=q[i-t[j]][j]*pow(1.0-p[j],(double)t[j]-1);            }            else                tmp=0;            dp[i%2][j]+=(dp[(i-1)%2][j]-tmp)*(1-p[j]);            dp[i%2][j+1]+=(dp[(i-1)%2][j]-tmp)*p[j]+tmp;            q[i][j+1]+=(dp[(i-1)%2][j]-tmp)*p[j]+tmp;            dp[(i-1)%2][j]=0;        }        dp[i%2][n]+=dp[(i-1)%2][n];        dp[(i-1)%2][n]=0;    }    double ans=0;    for(int i=0;i<=n;i++)    {        ans+=dp[k%2][i]*i;    }    printf("%.7f\n",ans);    return 0;}

 

codeforces284 div1 B:概率dp