程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 3853 向下向右找出口問題

HDU 3853 向下向右找出口問題

編輯:關於C++

題意:初始狀態在(1,1)的位置,目標是走到(n,n),每次只能向下向右或者不移動,已知在每個格子時這三種情況的概率,每移動一步消耗2的魔力,求走到終點的使用的魔力的期望。

分析:簡單的期望dp,套用之前的框架,但是這題不是+1,而是+2,因為每次多加的那個數字是走一步的消耗,這裡是2!注意p1[i][j]==1時不能計算dp[i][j],看式子就知道了,分母不能為0。

代碼:

 

#include
#include
using namespace std;
int n,m;
double p1[1005][1005],p2[1005][1005],p3[1005][1005],dp[1005][1005];
int main()
{
	while(scanf(%d%d,&n,&m)!=EOF){
		for(int i=0;i=0;i--){
			for(int j=m-1;j>=0;j--){
				if(i==n-1&&j==m-1) continue;
				if(p1[i][j]==1.0) continue;
				 dp[i][j]=p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2.0;
				dp[i][j]/=(1.0-p1[i][j]);
			}
		}
		printf(%.3lf
,dp[0][0]);
	}
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved