HDU3853 LOOPS
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853
题意：在一个n*m的网格中，你有一定的概率待在原地，向右走一格，向下走一格。每次操作都会消耗2个魔法，问从（1,1）走到（n,m）所需的魔法期望是多少。
思路：设dp[i][j]表示从(i,j)走到(n,m)还需要的魔法数。先找到期待值dp[n][m]=0，然后有（1-a[i][j].x）的概率是可以不待在原地的，再根据概率之间的一些转换可以得出：
dp[i][j]=(a[i][j].y*dp[i][j+1]+a[i][j].z*dp[i+1][j]+2)/(1-a[i][j].x);
#include<bits/stdc++.h> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; double dp[1010][1010]; struct node { double x,y,z; }a[1010][1010]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lf%lf%lf",&a[i][j].x,&a[i][j].y,&a[i][j].z); dp[n][m]=0; for(int i=n;i>=1;i--) for(int j=m;j>=1;j--) { if(i==n&&j==m) continue; if(a[i][j].x==1) continue; dp[i][j]=(a[i][j].y*dp[i][j+1]+a[i][j].z*dp[i+1][j]+2)/(1-a[i][j].x); } printf("%.3lf ",dp[1][1]); } }