hdu 3853 LOOPS 概率dp

hdu 3853 LOOPS 概率dp

題目大意

有一個人被困在一個 R*C(2<=R,C<=1000) 的迷宮中，起初他在 (1,1) 這個點，迷宮的出口是 (R,C)。在迷宮的每一個格子中，他能花費 2 個魔法值開啟傳送通道。假設他在 (x,y) 這個格子中，開啟傳送通道之後，有 p_lift[i][j] 的概率被送到 (x,y+1)，有 p_down[i][j] 的概率被送到 (x+1,y)，有 p_loop[i][j] 的概率被送到 (x,y)。問他到出口需要花費的魔法值的期望是多少。

簡單的求期望，弄懂求期望和求概率的區別就好很多了

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+Cjxicj4KCiAKPGJyPgpJbnB1dApUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMiA8PSBSLCBDIDw9IDEwMDApLjxicj4KPGJyPgpUaGUgZm9sbG93aW5nIFIgbGluZXMsIGVhY2ggY29udGFpbnMgQyozIHJlYWwgbnVtYmVycywgYXQgMiBkZWNpbWFsIHBsYWNlcy4gRXZlcnkgdGhyZWUgbnVtYmVycyBtYWtlIGEgZ3JvdXAuIFRoZSBmaXJzdCwgc2Vjb25kIGFuZCB0aGlyZCBudW1iZXIgb2YgdGhlIGN0aCBncm91cCBvZiBsaW5lIHIgcmVwcmVzZW50IHRoZSBwcm9iYWJpbGl0eSBvZiB0cmFuc3BvcnRhdGlvbiB0byBncmlkIChyLCBjKSwgZ3JpZCAociwgYyYjNDM7MSksIGdyaWQgKHImIzQzOzEsCiBjKSBvZiB0aGUgcG9ydGFsIGluIGdyaWQgKHIsIGMpIHJlc3BlY3RpdmVseS4gVHdvIGdyb3VwcyBvZiBudW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgNCBzcGFjZXMuPGJyPgo8YnI+Ckl0IGlzIGVuc3VyZWQgdGhhdCB0aGUgc3VtIG9mIHRocmVlIG51bWJlcnMgaW4gZWFjaCBncm91cCBpcyAxLCBhbmQgdGhlIHNlY29uZCBudW1iZXJzIG9mIHRoZSByaWdodG1vc3QgZ3JvdXBzIGFyZSAwIChhcyB0aGVyZSBhcmUgbm8gZ3JpZHMgb24gdGhlIHJpZ2h0IG9mIHRoZW0pIHdoaWxlIHRoZSB0aGlyZCBudW1iZXJzIG9mIHRoZSBkb3dubW9zdCBncm91cHMgYXJlIDAgKGFzIHRoZXJlIGFyZSBubyBncmlkcyBiZWxvdyB0aGVtKS48YnI+Cjxicj4KWW91IG1heSBpZ25vcmUgdGhlIGxhc3QgdGhyZWUgbnVtYmVycyBvZiB0aGUgaW5wdXQgZGF0YS4gVGhleSBhcmUgcHJpbnRlZCBqdXN0IGZvciBsb29raW5nIG5lYXQuPGJyPgo8YnI+ClRoZSBhbnN3ZXIgaXMgZW5zdXJlZCBubyBncmVhdGVyIHRoYW4gMTAwMDAwMC48YnI+Cjxicj4KVGVybWluYWwgYXQgRU9GPGJyPgo8YnI+Cjxicj4KCiAKPGJyPgpPdXRwdXQKQSByZWFsIG51bWJlciBhdCAzIGRlY2ltYWwgcGxhY2VzIChyb3VuZCB0byksIHJlcHJlc2VudGluZyB0aGUgZXhwZWN0IG1hZ2ljIHBvd2VyIEhvbXVyYSBuZWVkIHRvIGVzY2FwZSBmcm9tIHRoZSBMT09QUy48YnI+Cjxicj4KCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"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

#include
#include
#include
#include
using namespace std;
struct node
{
    double x,y,z;
} f[1012][1012];
double dp[1012][1012];
int main()
{
    int n,m;
    
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=0; i=0; i--)
        {
            for(int j=m-1; j>=0; j--)
            {
                if(i==n-1&&j==m-1)
                    continue;
                if(f[i][j].x!=1)
                {
                    dp[i][j]=dp[i][j+1]*f[i][j].y+dp[i+1][j]*f[i][j].z+1;
                    dp[i][j]/=(1-f[i][j].x);
                }
            }
        }
        printf("%.3lf\n",dp[0][0]*2);
    }
    return 0;
}