HDU 4576 Robot

Robot

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 148    Accepted Submission(s): 40

Problem Description

Michael has a telecontrol robot. One day he put the robot on a loop with n cells. The cells are numbered from 1 to n clockwise.



At first the robot is in cell 1. Then Michael uses a remote control to send m commands to the robot. A command will make the robot walk some distance. Unfortunately the direction part on the remote control is broken, so for every command the robot will chose a direction(clockwise or anticlockwise) randomly with equal possibility, and then walk w cells forward.
Michael wants to know the possibility of the robot stopping in the cell that cell number >= l and <= r after m commands.

 

Input

There are multiple test cases. 
Each test case contains several lines.
The first line contains four integers: above mentioned n(1≤n≤200) ,m(0≤m≤1,000,000),l,r(1≤l≤r≤n).
Then m lines follow, each representing a command. A command is a integer w(1≤w≤100) representing the cell length the robot will walk for this command.  
The input end with n=0,m=0,l=0,r=0. You should not process this test case.

 

Output

For each test case in the input, you should output a line with the expected possibility. Output should be round to 4 digits after decimal points.

 

Sample Input

3 1 1 2 1 5 2 4 4 1 2 0 0 0 0

 

Sample Output

0.5000 0.2500

 

Source

2013ACM-ICPC杭州赛区全国邀请赛

 

题意思路：

      机器人在开始在位置1，有一个环1-n，机器人有m个操作，每次都可以向前或向后走，求最后机器人在[l,r]范围内的概率。简单的DP递推。

      这个题我想说说我的看法，一开始我直接用map记录的次数TlE，改写dp概率数组用C提交加上读入优化可以过，这是基于此题N的规模（<=200）与测试数据的关系吧。

但是如果W巨大的时候利用map转移次数还是有优势的（个人看法，记得前年网络预选赛的一道关于时钟的DP就是利用的map,因为状态不多，也就是离散的原因比较快）。

 代码也就没有什么意义了。

#include <stdio.h>
#include <stdlib.h>
int getint(){
    char c=getchar();
    int t=0;
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c>='0'&&c<='9'){
       t=t*10+c-'0';
       c=getchar();
    }
   return t;
}
double dp[208] ,dp2[208];
int main(){
   int N , m ,l, r ,i,w,p,x;
   double ans;
   while(scanf("%d%d%d%d",&N,&m,&l,&r)!=EOF){
     if(N==0&&m==0&&l==0&&r==0)
         break ;
    memset(dp,0,sizeof(dp)) ;
    memset(dp2,0,sizeof(dp2)) ;
    dp[1]++ ;
    while(m--){
       //scanf("%d",&w) ;
       w=getint() ;
        for(p=1;p<=N;p++){
            if(dp[p]==0)
                continue ;
            x=(p+w)%N ;
            if(x==0)
                x=N ;
            dp2[x]+=0.5*dp[p] ;
            x=(p-w)%N ;
            if(x<=0)
                x=N+x ;
            dp2[x]+=0.5*dp[p];
        }
        for(i=1;i<=N;i++){
            dp[i]=dp2[i] ;
            dp2[i]=0 ;
        }
    }
    ans=0 ;
    for(i=l;i<=r;i++)
        ans+=dp[i] ;
    printf("%.4f
",ans) ;
   }
   return 0 ;
}

   N较大时的小技巧。

#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <set>
#include <map>
#include <limits.h>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std ;
struct Me{
  int M ,N;
  int L ,R ;
  map<int ,int>dp ,dp2;
  Me(){}
  Me(int n,int m ,int l ,int r):N(n),M(m),L(l),R(r){}
  void gao_qi(){
    int w ;
    dp.clear() ;
    dp2.clear() ;
    map<int,int>::iterator p ;
    dp[1]++ ;
    while(M--){
        scanf("%d",&w) ;
        for(p=dp.begin();p!=dp.end();p++){
            int x ;
            x=((p->first)+w)%N ;
            if(x==0)
                x=N ;
            dp2[x]+=(p->second) ;
            x=((p->first)-w)%N ;
            if(x<=0)
                x=N+x ;
            dp2[x]+=(p->second) ;
        }
        dp.clear() ;
        dp=dp2 ;
        dp2.clear() ;
    }
    double all ,show ;
    all=show=0 ;
    for(p=dp.begin();p!=dp.end();p++){
        all+=(p->second) ;
        if(L<=(p->first)&&(p->first)<=R)
            show+=(p->second) ;
    }
    printf("%.4lf
",show/all) ;
  }
};
int main(){
   int n , m ,l, r ;
   while(scanf("%d%d%d%d",&n,&m,&l,&r)){
     if(n==0&&m==0&&l==0&&r==0)
         break ;
     Me me(n,m,l,r) ;
     me.gao_qi() ;
   }
   return 0 ;
}