hdu 4576 （简单dp+滚动数组）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4576

题意：给出1~n的环，m个操作，每次能顺时针或逆时针走w步，询问最后在l~r这段区间内概率。
(1<=n<=200) ,(0<=m<=1,000,000),(1<=l<=r<=n).
分析：每次从某一个数字到达另外数字的概率为0.5，按概率dp求出到达每个数字的概率，然后枚举从l到r的概率相加即可。
dp[i][j]表示第i次操作落在数字j上的概率，但是不能直接开1000000*200的数组来保存中间结果，这肯定是会爆掉的。
因为每次只需要取上一次的数据，所以可以用滚动数组，开dp[2][200]就行了
注意：w可能比n大，所以要先w%n
这一题卡时限卡的非常紧，代码稍微写挫一点就会超时了。
代码如下：

 #include<stdio.h>

 #include<string.h>

 double dp[][];

 int main()

 {

     int n,m,l,r,i,t,k,w;

     while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF)

     {

         if(n==&&m==&&l==&&r==)

             break;

         memset(dp,,sizeof(dp));

         dp[][]=;

         t=;

         while(m--)

         {

             scanf("%d",&w);

             w%=n;

             k=t^;

             for(i=;i<n;i++)

                 dp[k][i]=;

             for(i=;i<n;i++)

             {

                 if(!dp[t][i])   //时限卡的很紧，加这一句来优化，减少运算次数

                     continue;

                 dp[k][(i+w)%n]+=0.5*dp[t][i];

                 dp[k][(i-w+n)%n]+=0.5*dp[t][i];

             }

             t=k;

         }

         double ans=;

         for(i=l;i<=r;i++)

             ans+=dp[t][i-];

         printf("%.4lf\n",ans);

     }

     return ;

 }

巴特西

hdu 4576 （简单dp+滚动数组）

最新文章

热门文章