首页 > 代码库 > HDU3853 LOOPS 概率DP

HDU3853 LOOPS 概率DP

十多分钟做出来了呃,虽然是入门级别的题目,但是还算是比较开心了呵呵

题意:

从一张r*c的图中 由左上角走向右下角,每一步 有一定概率不动,也有一定概率往下,还有一定概率向由走一步,每一次花费2

方程: 是最一般的思路,以目标状态为边界,当前状态到目标状态所需期望  为方程

dp[i][j]  代表在(i,j)到目标 需要的期望

那么很显然dp[i][j] = dp[i + 1][j] * mp[i][j][1] + dp[i][j + 1] * mp[i][j][0] + dp[i][j] * mp[i][j][2] + 2;

方程右边也有一个dp[i][j],所以要移过来,

边界:dp[r - 1][c - 1]很显然为0,因为相当于自己到自己的 期望


还有注意点,有可能当前点 不动的概率为1,那么当前点算是一个死点,也就是dp[i][j]应该为0,因为他不可能抵达目标状态


int r,c;

double dp[1000 + 55][1000 + 55];

double mp[1000 + 55][1000 + 55][3];

void init() {

}

bool input() {
	while(cin>>r>>c) {
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				cin>>mp[i][j][0]>>mp[i][j][1]>>mp[i][j][2];
			}
		}
		return false;
	}
	return true;
}

void cal() {
	dp[r - 1][c - 1] = 0.00;
	for(int i=r - 1;i>=0;i--) {
		for(int j=c - 1;j>=0;j--) {
			if(i == r - 1 && j == c - 1)continue;
			if(mp[i][j][0] == 1.00)continue;
			//if(i == r - 1)dp[i][j] = dp[i][j + 1] * mp[i][j][0] + dp[i][j] * mp[i][j][2] + 2;
			//else if(j == c - 1)
			//	dp[i][j] = dp[i + 1][j] * mp[i][j][1] + dp[i][j] * mp[i][j][2] + 2;
			//else 
				dp[i][j] = dp[i + 1][j] * mp[i][j][2] + dp[i][j + 1] * mp[i][j][1] + 2;
				dp[i][j] /= (1 - mp[i][j][0]);
		}
	}
	printf("%.3lf\n",dp[0][0]);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}


HDU3853 LOOPS 概率DP