확률 DP: 플라잉 바둑 hdu4405

2853 단어 dp
Description Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When Hzz is at grid i and the dice number is x, he will moves to grid i+x. Hzz finishes the game when i+x is equal to or greater than N.
There are also M flight lines on the chess map. The i-th flight line can help Hzz fly from grid Xi to Yi (0 
#include 
#include 
using namespace std;
int n,m,t1,t2, fly[100009];
double dp[100009];
int main()
{
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        memset(fly,-1,sizeof fly);
        memset(dp,0,sizeof dp);
        while(m--)
        {
            int t2,t1;
            scanf("%d%d",&t1,&t2);
            fly[t1]=t2;
        }
        for(int i=n-1;i>=0;i--)
        {
            if(fly[i]!=-1)
                dp[i]=dp[fly[i]];
            else
            {
                for(int j=1;j<=6;j++)
                    dp[i]+=dp[i+j];
                    dp[i]=dp[i]/6+1;
            }
        }
        printf("%.4f
",dp[0]);
    }
    return 0;
}

사고방식: 1. 만약에 직접 비행할 수 없다면 한 위치에서 여섯 개의 다른 위치로 출발할 수 있다. 확률은 이 위치와의 합이다. 여섯 가지 기회가 균등할 수 있기 때문에 결과는 6을 제외하고 1(어디를 가든지 첫 번째 주사위를 던질 수 있다. 2. 직접 비행할 수 있다면 이 위치로 날아갈 확률이다.
Flow가 받은 값을 데이터로 변환하기 위해 Mutable LiveData로 변환
배운 것 총결산

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage