?
求从【1,1】到【r,c】的所花power的期望，每走一步消耗的power是2，给出从[i,j]到[i,j]，[i,j+1]，[i+1][j]概率。
dp[i][j]表示从[i,j]到[r,c]的消耗power的期望，已知终态dp[r][c] = 0，然后逆推。
很难想的是当在原地的概率为1时，走不到[r,c]，状态转移方程中结果是INF，与题目要求相矛盾。
#include #include #include #include #include #include #include #include #include #include #include #include #include //#define LL __int64 #define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; double dp[1010][1010]; double a[1010][3010]; int main() { int n,m; while(~scanf(%d %d,&n,&m)) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= 3*m; j++) scanf(%lf,&a[i][j]); } memset(dp,0.0,sizeof(dp)); dp[n][m] = 0; int flag = 1; for(int i = n; i >= 1; i--) { for(int j = m; j >= 1; j--) { if(i == n && j == m) continue; if(fabs(1.0 - a[i][(j-1)*3+1]) < eps) //重点 { continue; } dp[i][j] = ( dp[i][j+1]*a[i][3*(j-1)+2] + dp[i+1][j]*a[i][j*3] + 2)/(1.0 - a[i][(j-1)*3+1]); } if(flag == 0) break; } printf(%.3lf ,dp[1][1]); } return 0; }