hdu 3853 LOOPS(기대)
1521 단어 확률 DP
[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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2151 Check the difficulty of problems(확률 DP)문제의 풀이는 (모든 팀이 최소한 한 문제를 풀 확률-모든 팀이 1에서 N-1 사이를 풀 확률) DP 상태를 설계할 때 DP 과정에서 어떤 문제를 기록해야 하는지 기록하기 어려우므로 일반적으로 DP의 과정을 방향이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.