확률 dp
5536 단어 HDU
총 n+1개 칸: 0-n
처음에 0번 칸에서 주사위를 던져서 전진하는 칸 수를 정합니다.
이외에 일부 전송문은 순식간에 u점에서 v점으로 전송할 수 있다(반드시 전송되어야 한다)
n점까지 걸어가려면 총 몇 번의 주사위를 던져야 합니까
분석:
너무 약해서 n^2의 dp방정식만 생각했어요. 아쉽게도 n은 100000...한참을 고민하다가 또 큰 소의 문제를 보았다
dp[i]로 i번째 점에 도착했을 때의 기대 p[i]로 i번째 점의 확률을 기록합니다...
이 확률 기록의 느낌은 비교적 신기하다. 내가 먼저 생각한 n^2는 i보로 j점까지 걸어갈 확률을 기록하는 것이다.
문제를 풀 확률은??평균 후의???f 어차피 이 시간까지 갈 확률
dp[i]=횟수*p 그러면 i+j점 dp[i+j]=(횟수+1)*p*1/6=(dp[i]+p[i])/6;
전이 방정식을 쓸 수 있어요.
동시에 next수 그룹 기록 전송문을 유지합니다. 만약 next[i]!=i는 i점에 멈출 수 없기 때문에 이 점을 통해 직접 continue로 이동하지 않고 i의 정보를 nxt[i]에 저장합니다
정답을 집계할 때는 n부터 n+5까지의 합을 주의해야 한다.
ac 코드:
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
int n,m;
int next[100010];
double dp[100010];
double p[100010];
void ini()
{
memset(dp,0,sizeof(dp));
memset(p,0,sizeof(p));
for(int i=0;i<=100000;i++)
{
next[i]=i;
}
int u,v;
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
next[u]=v;
}
}
void solve()
{
dp[0]=0;
p[0]=1;
for(int i=0;i<n;i++)
{
if(next[i]!=i)
{
p[next[i]]+=p[i];
dp[next[i]]+=dp[i];
p[i]=0;
continue;
}
for(int j=1;j<=6;j++)
{
p[i+j]+=p[i]*1.0/6.0;
dp[i+j]+=(dp[i]+p[i])*1.0/6.0;
}
}
double ans=0;
for(int i=n;i<n+6;i++)
{
ans+=dp[i];
}
printf("%.4f
",ans);
}
int main()
{
while(scanf("%d%d",&n,&m),m+n)
{
ini();
solve();
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
