首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。