HDU 4576 Robot （概率DP）

//hdu robot   
#include <cstdio>   
#include <iostream>   
#include <cmath>   
#include <cstring>   
using namespace std;  
  
inline void RD(int &ret) {  
    char c;  
    do {  
        c = getchar();  
    } while(c < '0' || c > '9') ;  
    ret = c - '0';  
    while((c=getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + ( c - '0' );  
}  
  
int n,m,l,r,w;  
double dp[2][222]; //第i步操作在j點的概率   
int main() {  
    while(scanf("%d%d%d%d",&n,&m,&l,&r) != EOF){  
        if(n == 0 && m == 0 && l == 0 && r == 0) break;  
        for(int i=0; i<n; i++) dp[0][i] = 0;  
        dp[0][0] = 1;  
        int cur = 0;  
        while(m --) {  
            RD(w);  
            for(int j=0; j<n; ++j) { //卡常數優化 ，如果從1-n的話，得變成i <= n，需要多判斷i是否等於n   
                dp[1 - cur][j] = dp[cur][(j+w) % n] * 0.5 + dp[cur][(j - w + n) % n] * 0.5;  
            }  
            cur = 1 - cur;  
        }  
        double ans = 0;  
        for(int i=l-1; i<r; ++i) {  
            ans += dp[cur][i];  
        }  
        printf("%.4f\n",ans);  
    }  
    return 0;  
}  

//hdu robot
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}

int n,m,l,r,w;
double dp[2][222]; //第i步操作在j點的概率
int main() {
    while(scanf("%d%d%d%d",&n,&m,&l,&r) != EOF){
        if(n == 0 && m == 0 && l == 0 && r == 0) break;
        for(int i=0; i<n; i++) dp[0][i] = 0;
        dp[0][0] = 1;
        int cur = 0;
        while(m --) {
            RD(w);
            for(int j=0; j<n; ++j) { //卡常數優化 ，如果從1-n的話，得變成i <= n，需要多判斷i是否等於n
                dp[1 - cur][j] = dp[cur][(j+w) % n] * 0.5 + dp[cur][(j - w + n) % n] * 0.5;
            }
            cur = 1 - cur;
        }
        double ans = 0;
        for(int i=l-1; i<r; ++i) {
            ans += dp[cur][i];
        }
        printf("%.4f\n",ans);
    }
    return 0;
}