HDU 4576 Robot(概率dp)

题目

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

有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 ;

}

HDU 4576 Robot(概率dp)的相关教程结束。