확률 dp

제목:
총 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[i]=횟수*p 그러면 i+j점 dp[i+j]=(횟수+1)*p*1/6=(dp[i]+p[i])/6;
전이 방정식을 쓸 수 있어요.
동시에 next수 그룹 기록 전송문을 유지합니다. 만약 next[i]!=i는 i점에 멈출 수 없기 때문에 이 점을 통해 직접 continue로 이동하지 않고 i의 정보를 nxt[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 10000

int 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
",ans);

}

int main()

{

    while(scanf("%d%d",&n,&m),m+n)

    {

        ini();

        solve();

    }

    return 0;

}