首页 > 代码库 > HDU_3853_概率dp
HDU_3853_概率dp
http://acm.hdu.edu.cn/showproblem.php?pid=3853
又因为总期望为子期望的加权和,加权因子为子期望的转移概率,所以得到:
dp[ i ][ j ]= p1 * ( dp[ i ][ j ] + 2 ) + p2 * ( dp[ i ][ j + 1 ] + 2 ) + p3 * ( dp[ i + 1 ][ j ] + 2) 。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int c,r;double ans[1005][1005],stay[1005][1005],rightt[1005][1005],down[1005][1005];int main(){ while(~scanf("%d%d",&r,&c)) { memset(ans,0,sizeof(ans)); for(int i = 1;i <= r;i++) { for(int j = 1;j <= c;j++) scanf("%lf%lf%lf",&stay[i][j],&rightt[i][j],&down[i][j]); } for(int i = r;i >= 1;i--) { for(int j = c;j >= 1;j--) { if(-1e-6 <= stay[i][j]-1 && stay[i][j]-1 <= 1e-6) continue; ans[i][j] = (2+rightt[i][j]*ans[i][j+1]+down[i][j]*ans[i+1][j])/(1-stay[i][j]); } } printf("%.3f\n",ans[1][1]); } return 0;}
HDU_3853_概率dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。