首页 > 代码库 > hdu4405：概率dp

hdu4405：概率dp

2024-07-25 02:34:10   222人阅读

题意：

总共有n+1个格子：0-n

初始情况下在 0号格子 每次通过掷骰子确定前进的格子数

此外 还有一些传送门可以瞬间从 u 点传送到 v 点（必须被传送）

求走到（或超过）n点总共需要掷多少次骰子

分析：

太弱 只想到了n^2的 dp方程 可惜n是100000...纠结半天又看了大牛的题解

用 dp[i]记录 走到第 i 个点时的期望 p[i]记录第 i 个点的概率。。、

这个概率记录的感觉比较神奇 ，我先开始想到的n^2是记录用 i 步 走到 j 点的概率

题解的这个概率应该是？？平均后的？？？f反正就是走到这个点了的概率直接把步数省去了 dp方程就少了一维 

dp[i]=次数 * p 那么 如果对于 i+j 点 dp[i+j]= （次数+1）*p*1/6 = ( dp[i]+p[i] ) / 6;

就可以写出转移方程了

同时在维护一个next数组记录 传送门 如果next[i]!=i 则证明不可能停在第 i 点 因此就不通过此点进行转移 直接continue，并把 i 的信息保存在next[i]中

统计答案的时候注意要统计 n到 n+5的和

ac代码：

#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000int n,m;int next[100010];double dp[100010];double p[100010];void ini(){    memset(dp,0,sizeof(dp));    memset(p,0,sizeof(p));    for(int i=0;i<=100000;i++)    {        next[i]=i;    }    int u,v;    for(int i=0;i<m;i++)    {        scanf("%d%d",&u,&v);        next[u]=v;    }}void solve(){    dp[0]=0;    p[0]=1;    for(int i=0;i<n;i++)    {        if(next[i]!=i)        {            p[next[i]]+=p[i];            dp[next[i]]+=dp[i];            p[i]=0;            continue;        }        for(int j=1;j<=6;j++)        {            p[i+j]+=p[i]*1.0/6.0;            dp[i+j]+=(dp[i]+p[i])*1.0/6.0;        }    }    double ans=0;    for(int i=n;i<n+6;i++)    {        ans+=dp[i];    }    printf("%.4f\n",ans);}int main(){    while(scanf("%d%d",&n,&m),m+n)    {        ini();        solve();    }    return 0;}

 

hdu4405：概率dp


联系
我们