HDU 4405(확률 DP)

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=4405

제목 대의:비행 기.만약 격자 가 비행 점 이 아니라면,주사 위 를 던 져 앞으로 나 아가 라.그렇지 않 으 면 바로 목표 지점 으로 날 아 갈 것 이다.각 칸 은 유일한 비행 출발점 이지 만 유일한 비행 종점 은 아니다.도착 하거나 결승점 을 넘 는 주사위 던 지기 기대 수 를 묻는다.
문제 풀이 방향:
기 대 를 바 라 는 것 은 바로 미 루 는 것 이 아니 라 역 추 해 야 한 다 는 것 을 알려 주 는 문제.
만약 에 추진 하고 있다 면 한 점 i 에 대해 비행 종점 이 라면 세 는 그의 비행 출발점 에 도착 해 야 합 니 다.출발점 이 여러 개 있 고 모든 출발점 의 확률 이 반드시 같 지 않 습 니 다.어떻게 구 하 기 를 바 랍 니까?
역 추진(종점 이 기점 으로 변 함)하면 한 점 i 에 대해 비행 기점 이 라면 매 거 진 비행 종점 을 확보 할 수 있 습 니 다.
즉,dp[v]=dp[i](v 는 i 의 종점),즉 v 점 은 주사 위 를 던 지지 않 아 도 되 고 기 대 는 i 점 의 기대 와 같 으 며 가장 중요 한 것 은 v 가 한 번 밖 에 나타 나 지 않 는 다 는 것 이다.
비행 점 이나 출발점(기점 기대=0)이 라면 주사 위 를 던 지지 않 아 도 되 기 때문에 v 점 을 매 거 할 때 미리 표 시 를 해 야 한다.이렇게 하면 이 점 에 주사 위 를 던 지지 않 아 도 된다.
보통 점 이 라면 i+1~i+6 등 확률 적 인 점 에 대한 기대/6 을 매 거 진 하고 주사 위 를 한 번 더 던 져 기대+1 을 한다.
마지막 으로 ans=dp[0].

#include "cstdio"

#include "vector"

#include "cstring"

using namespace std;

vector<int> air[100005];

double dp[100005];

bool vis[100005];

int main()

{

    //freopen("in.txt","r",stdin);

    int n,m,u,v;

    while(scanf("%d%d",&n,&m)!=EOF&&n)

    {

        memset(dp,0,sizeof(dp));

        memset(vis,false,sizeof(vis));

        for(int i=0;i<=n;i++) air[i].clear();

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            air[v].push_back(u);

        }

        for(int i=n;i>=0;i--)

        {

            if(!vis[i]&&i!=n)

            {

                for(int j=i+1;j<=i+6;j++) dp[i]+=dp[j]/6;

                dp[i]+=1;

            }

            for(int j=0;j<air[i].size();j++)

            {

                int to=air[i][j];

                dp[to]=dp[i];

                vis[to]=true;

            }

        }

        printf("%.4lf
",dp[0]);

    }

}

12186624
2014-11-14 21:25:00
Accepted
4405
15MS
2720K
920 B
C++
Physcal

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU] 4089 활성화 확률 DP

dp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 4405(확률 DP)

좋은 웹페이지 즐겨찾기