hdu 3853 LOOPS(기대)

1521 단어 확률 DP
http://acm.hdu.edu.cn/showproblem.php?pid=3853
[1,1]에서[r,c]까지 쓰 는 power 의 기 대 를 구하 고 한 걸음 한 걸음 소모 하 는 power 는 2 이 며[i,j]에서[i,j],[i,j+1],[i+1][j]확률 을 제시 합 니 다.
dp[i][j]는[i,j]에서[r,c]까지 파워 를 소모 하 는 기 대 를 나타 내 고 종 태 dp[r][c]=0 을 알 고 역 추 를 한다.
제자리 에 있 을 확률 이 1 일 때[r,c]에 가지 못 하고 상태 전이 방정식 에서 결 과 는 INF 로 제목 요구 와 모순 된다 고 생각 하기 어렵다.
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
//#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; }

좋은 웹페이지 즐겨찾기