HDOJ 3853 LOOPS (DP 기대 입문)

제목: r * c 의 격자 지도, 출발점 은 (1, 1) 이 고 종점 은 (r, c) 이 며 방향 은 세 가지 만 있 습 니 다. 제자리 에 있 고 오른쪽으로 가 며 아래로 내 려 갑 니 다. 한 걸음 걸 을 때마다 2 입 니 다.각 점 세 가지 방향 으로 갈 확률 을 제시 하고 출발점 에서 종점 까지 가 는 기대 비용 을 구한다.기왕 기 대 를 바 라 는 바 에 야 거꾸로 걸 어 라.dp [i] [j] 를 설정 하 는 것 은 (i, j) 점 에 있 을 때 종점 에 도착 하 는 기대 걸음 수 입 니 다. 기대 하 는 선형 관계 로 인해 몇 개의 키 기대 에서 구 할 수 있 기 를 기대 합 니 다. 그러면 (i, j) 점 의 세 가지 방향 에 대해 다음 단계 에 도착 할 수 있 습 니 다.   （i，j）,（i，j+1），（i+1，j）； 가설 확률 은 각각 p [1], p [2], p [3] 이다.그러면 기대 공식 에서 얻 을 수 있 는 것 은 dp [i] [j] = p [1] * dp [i] [j] + p [2] * dp [i] [j + 1] + p [3] * dp [i + 1] [j] + 2;요약: dp [i] [j] = (p [2] * dp [i] [j + 1] + p [3] * dp [i + 1] [j] + 2) / (1 - p [1]);이동 이 완료 되 었 습 니 다.경계 고려: dp [r] [c] = 0;
기대 감 이 상태 에 대한 전이 가 어렵 기 를 바 랍 니 다. 이 점 의 모든 다음 상 태 를 잘 고려 한 다음 에 그 확률 을 곱 한 다음 에 기대 * 자 확률 을 누적 해 야 합 니 다.그러면 아버지 가 원 하 시 는 것 이 나 옵 니 다. 공식 은 바로 E (aX + bY) = a * E (X) + b * E (Y) 입 니 다.
ps: 수학 을 잘 못 하면 경상 이에 요.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int r,c;
double dp[1005][1005],p[1005][1005][4];
int main()
{
    while(scanf("%d%d",&r,&c)!=EOF)
    {
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                for(int k=1;k<=3;k++)
                    scanf("%lf",&p[i][j][k]);
            }
        }
        dp[r][c]=0;
        for(int i=r;i>=1;i--)
        {
            for(int j=c;j>=1;j--)
            {
                if(i==r&&j==c||p[i][j][1]==1)
                    continue;
                dp[i][j]=(p[i][j][2]*dp[i][j+1]+p[i][j][3]*dp[i+1][j]+2)/(1.0-p[i][j][1]);
            }
        }
        printf("%.3f
",dp[1][1]);
    }
return 0;
}