程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3853 LOOPS(期望)

hdu 3853 LOOPS(期望)

編輯:C++入門知識

hdu 3853 LOOPS(期望)


 

求從【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;
}


 

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