学步园

概率DP 水题

#include<iostream>
using namespace std;
struct node{
	double a,b,c;
}p[1005][1005];
double dp[1005][1005];
int main(){
	int r,c;
	while(cin>>r>>c){
		int i,j;
		for( i=1;i<=r;i++){
			for(j=1;j<=c;j++)
				scanf("%lf%lf%lf",&p[i][j].a,&p[i][j].b,&p[i][j].c);
		}
		dp[r][c]=0;
		//dp[i][j]表示从位置（i,j)到达终点的期望，
		//则dp[i][j]=(2+dp[i][j])*sa[i][j][0]+(2+dp[i][j+1])*sa[i][j][1]+(2+dp[i+1][j])*sa[i][j][2],
		//移向即可得转移方程。
		for(i=r;i>=1;i--){
			for(j=c;j>=1;j--){
				if(i==r && j==c)
					continue;
				if( p[i][j].a==1 )
					continue;
				dp[i][j]=( dp[i][j+1]*p[i][j].b+dp[i+1][j]*p[i][j].c+2)/(1-p[i][j].a);
			}
		}
		printf("%.3lf\n",dp[1][1]);
	}
	return 0;
}