http://acm.hdu.edu.cn/showproblem.php?pid=3853
題意:n×m的格子,起始在(1,1),要求走到(n,m),在每一格(i,j)有三種走法,其中p[i,j,0]的概率留在原地,p[i,j,1]的概率走到(i,j+1),p[i,j,2]的概率走到(i+1, j),問(wèn)期望步數(shù)。(n,m<=1000)
#include <cstdio> #include <cstring> using namespace std; const int N=1005; int n, m; double p[N][N][3], d[N][N]; const double eps=1e-10; double abs(double x) { return x<0?-x:x; } int main() { while(~scanf("%d%d", &n, &m)) { memset(d, 0, sizeof d); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) for(int k=0; k<3; ++k) scanf("%lf", &p[i][j][k]); for(int i=n; i>=1; --i) for(int j=m; j>=1; --j) if(!(i==n&&j==m) && abs(1-p[i][j][0])>eps) d[i][j]=(d[i][j+1]*p[i][j][1]+d[i+1][j]*p[i][j][2]+2)/(1-p[i][j][0]); printf("%.3f\n", d[1][1]); } return 0; }
裸題= =分類討論之..由于互斥然后線性求一下就行了= =
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
