HDU 3853 LOOPS (概率dp)

LOOPS

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)

Total Submission(s): 2931 Accepted Submission(s): 1209

Problem Description Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl).

Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth called LOOPS.

The planform of the LOOPS is a rectangle of R*C grids. There is a portal in each grid except the exit grid. It costs Homura 2 magic power to use a portal once. The portal in a grid G(r, c) will send Homura to the grid below G (grid(r+1, c)), the grid on the right of G (grid(r, c+1)), or even G itself at respective probability (How evil the Boss Incubator is)!
At the beginning Homura is in the tZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcCBsZWZ0IGNvcm5lciBvZiB0aGUgTE9PUFMgKCgxLCAxKSksIGFuZCB0aGUgZXhpdCBvZiB0aGUgbGFieXJpbnRoIGlzIGluIHRoZSBib3R0b20gcmlnaHQgY29ybmVyICgoUiwgQykpLiBHaXZlbiB0aGUgcHJvYmFiaWxpdHkgb2YgdHJhbnNtaXNzaW9ucyBvZiBlYWNoIHBvcnRhbCwgeW91ciB0YXNrIGlzIGhlbHAgcG9vciBIb211cmEgY2FsY3VsYXRlIHRoZSBFWFBFQ1QgbWFnaWMgcG93ZXIKIHNoZSBuZWVkIHRvIGVzY2FwZSBmcm9tIHRoZSBMT09QUy48YnI+Cjxicj4KPGJyPgo8YnI+CklucHV0IAoKVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDIgPD0gUiwgQyA8PSAxMDAwKS48YnI+Cjxicj4KVGhlIGZvbGxvd2luZyBSIGxpbmVzLCBlYWNoIGNvbnRhaW5zIEMqMyByZWFsIG51bWJlcnMsIGF0IDIgZGVjaW1hbCBwbGFjZXMuIEV2ZXJ5IHRocmVlIG51bWJlcnMgbWFrZSBhIGdyb3VwLiBUaGUgZmlyc3QsIHNlY29uZCBhbmQgdGhpcmQgbnVtYmVyIG9mIHRoZSBjdGggZ3JvdXAgb2YgbGluZSByIHJlcHJlc2VudCB0aGUgcHJvYmFiaWxpdHkgb2YgdHJhbnNwb3J0YXRpb24gdG8gZ3JpZCAociwgYyksIGdyaWQgKHIsIGMmIzQzOzEpLCBncmlkIChyJiM0MzsxLAogYykgb2YgdGhlIHBvcnRhbCBpbiBncmlkIChyLCBjKSByZXNwZWN0aXZlbHkuIFR3byBncm91cHMgb2YgbnVtYmVycyBhcmUgc2VwYXJhdGVkIGJ5IDQgc3BhY2VzLjxicj4KPGJyPgpJdCBpcyBlbnN1cmVkIHRoYXQgdGhlIHN1bSBvZiB0aHJlZSBudW1iZXJzIGluIGVhY2ggZ3JvdXAgaXMgMSwgYW5kIHRoZSBzZWNvbmQgbnVtYmVycyBvZiB0aGUgcmlnaHRtb3N0IGdyb3VwcyBhcmUgMCAoYXMgdGhlcmUgYXJlIG5vIGdyaWRzIG9uIHRoZSByaWdodCBvZiB0aGVtKSB3aGlsZSB0aGUgdGhpcmQgbnVtYmVycyBvZiB0aGUgZG93bm1vc3QgZ3JvdXBzIGFyZSAwIChhcyB0aGVyZSBhcmUgbm8gZ3JpZHMgYmVsb3cgdGhlbSkuPGJyPgo8YnI+CllvdSBtYXkgaWdub3JlIHRoZSBsYXN0IHRocmVlIG51bWJlcnMgb2YgdGhlIGlucHV0IGRhdGEuIFRoZXkgYXJlIHByaW50ZWQganVzdCBmb3IgbG9va2luZyBuZWF0Ljxicj4KPGJyPgpUaGUgYW5zd2VyIGlzIGVuc3VyZWQgbm8gZ3JlYXRlciB0aGFuIDEwMDAwMDAuPGJyPgo8YnI+ClRlcm1pbmFsIGF0IEVPRjxicj4KPGJyPgo8YnI+CgpPdXRwdXQgCkEgcmVhbCBudW1iZXIgYXQgMyBkZWNpbWFsIHBsYWNlcyAocm91bmQgdG8pLCByZXByZXNlbnRpbmcgdGhlIGV4cGVjdCBtYWdpYyBwb3dlciBIb211cmEgbmVlZCB0byBlc2NhcGUgZnJvbSB0aGUgTE9PUFMuPGJyPgo8YnI+CgogClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="brush:java;">2 2 0.00 0.50 0.50 0.50 0.00 0.50 0.50 0.50 0.00 1.00 0.00 0.00 Sample Output

6.000

Source 2011 Invitational Contest Host by BUPT

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3853

題目大意：一個r*c的迷宮，每個位置有三個分別為傳送到grid (r, c), grid (r, c+1), grid (r+1, c)的概率，每次要花2魔法值，求從起點(1, 1)到終點(r, c)魔法值的期望

題目分析：簡單的概率dp，用p[0][i][j]，p[1][i][j]，p[2][i][j]分別表示每個點的三個對應概率，dp[i][j]表示從(i,j)到(r,c)魔法值的期望，則可得到轉移方程：
dp[i][j]＝dp[i][j] * p[0][i][j] + dp[i][j + 1] * p[1][i][j] + dp[i + 1][j] * p[2][i][j]
==> dp[i][j] = (dp[i][j + 1] * p[1][i][j] + dp[i + 1][j] * p[2][i][j]) / (1.0 - p[0][i][j])
從這個轉移方程不難看出從dp[r][c]向前推就行了，dp[r][c] = 0，還有要注意分母為0的情況要特判，如果p[0][i][j] ＝ 1，則顯然是個死循環，dp[i][j] = 0

#include 
#include 
int const MAX = 1005;
double const EPS = 1e-10;
double p[3][MAX][MAX], dp[MAX][MAX];

int main()
{
    int r, c;
    double p1, p2, p3;
    while(scanf("%d %d", &r, &c) != EOF)
    {
        for(int i = 1; i <= r; i++)
            for(int j = 1; j <= c; j++)
                scanf("%lf %lf %lf", &p[0][i][j], &p[1][i][j], &p[2][i][j]);
        dp[r][c] = 0;
        for(int i = r; i >= 1; i--)
            for(int j = c; j >= 1; j--)
                if(!(i == r && j == c))
                    if(fabs(p[0][i][j] - 1.0) < EPS)
                        dp[i][j] = 0;
                    else 
                        dp[i][j] = (dp[i][j + 1] * p[1][i][j] + dp[i + 1][j] * p[2][i][j] + 2) / (1.0 - p[0][i][j]);
        printf("%.3f\n", dp[1][1]);
    }
}