HDU 4576 Robot(概率dp)

时间:2021-02-03 10:04:04

题目

/*********************复制来的大致题意**********************

有N个数字,M个操作, 区间L, R。 然后问经过M个操作后落在[L, R]的概率。

*******************************************************/

//自己做,错掉了,然后参考了别人的解法,说是要 概率dp

//概率模拟题,一定要用概率来模拟,

//因为数据很大,可能超了__int64,

//模拟方式用dp[2][], 0表示前一个状态,1表示现在的状态,

//WA掉的解法:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int main()
{
int n,m,l,r,w,i,j;
__int64 a[],a1[];
int temp1,temp2,temp;
__int64 fenzi,fenmu; while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF)
{
if(n==&&m==&&l==&&r==)break;
memset(a,,sizeof(a));
memset(a1,,sizeof(a1));
a[]=;
a1[]=; for(i=;i<m;i++)
{
scanf("%d",&w);
w=w%n;
for(j=;j<=n;j++)
{
if(a[j]!=)
{
temp=a[j];
temp1=j+w;
while(temp1>n)temp1=temp1-n;
temp2=j-w;
while(temp2<)temp2=temp2+n;
a1[temp1]+=a[j];
a1[temp2]+=a[j];
a1[j]=a1[j]-temp;
}
}
for(j=;j<=n;j++)
{
a[j]=a1[j];
}
} fenzi=;
fenmu=;
for(j=;j<=n;j++)
{
fenmu=fenmu+a[j];
}
for(j=l;j<=r;j++)
{
fenzi=fenzi+a[j];
} printf("%.4lf\n",(fenzi*1.0)/(fenmu*1.0)); }
return ;
}

//我猜测搓掉的原因是数据太大,导致越界,然后结果就不准了,因为m很大哦~

//可以AC的解法:

//听说这种解法叫做简单的概率dp
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int n,m,l,r,w,i,j;
int temp1,temp2,temp;
double dp[][]; //0 1 表示前后两次,210 表示点 dp 概率 while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF)
{
if(n==&&m==&&l==&&r==)break;
memset(dp,,sizeof(dp));
dp[][]=;
temp = ; //状态 0 1
for(i=;i<=m;i++)
{
scanf("%d",&w);
for(j=;j<=n;j++)
{
temp1=j+w;
while(temp1>n)temp1=temp1-n;
temp2=j-w;
while(temp2<)temp2=temp2+n;
dp[(temp+)%][temp1]+=dp[temp][j]*0.5;
dp[(temp+)%][temp2]+=dp[temp][j]*0.5;
dp[temp][j]=;
}
temp=(temp+)%;
}
double ans = 0.0;
for(i=l;i<=r;i++)
{
ans+=dp[temp][i];
}
printf("%.4lf\n",ans);
}
return ;
}