求從【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; }
linux下通過top或vmstat查看系統CPU占用
Problem Description LL最近沉迷於
Interpolation methods,interpol
C++標准模板庫與數據結構的學習 STL(Stand
此文總結常用vector操作,是前一篇的續作!只有代碼
HDOJ 1348 Wall 凸包 &nb