HDU - 4576 Robot（概率dp+滚动数组）

题意：所有的格子围成一个圈，标号为1~n，若从格子1出发，每次指令告知行走的步数，但可能逆时针也可能顺时针走，概率都是1/2，那么问走了m次指令后位于格子l~r(1≤l≤r≤n)的概率。

分析：

1、因为m次指令后不知道会走到哪，会有很多种可能，但是知道从哪里出发，所以起始状态是已知的，在最初的状态，位于格子1是必然的，概率为1。

2、本题应用滚动数组，因为每次指令后都会延伸出无数种可能，这些可能是在前一种状态的基础上延伸的，而且延伸过后前一种状态的值不再有意义，完全可以被当前状态所覆盖。

3、从tmp1和tmp2逆时针或顺时针走w步则会到达位置i，概率都为0.5，dp[1 - u][i] = 0.5 * dp[u][tmp1] + 0.5 * dp[u][tmp2]。

4、因为位置范围是1~n，取余会超时，

if(tmp1 <= 0) tmp1 += n;
if(tmp2 > n) tmp2 -= n;

这样处理就好了。

5、最后统计一下m次指令后位于格子l~r的概率之和。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 200 + 10;

const int MAXT = 1000000 + 10;

using namespace std;

double dp[2][MAXN];

int main(){

    int n, m, l, r;

    while(scanf("%d%d%d%d", &n, &m, &l, &r) == 4){

        if(!n && !m && !l && !r) return 0;

        memset(dp, 0, sizeof dp);

        dp[0][1] = 1;

        int u = 0;

        while(m--){

            int w;

            scanf("%d", &w);

            for(int i = 1; i <= n; ++i){

                int tmp1 = i - w;

                int tmp2 = i + w;

                if(tmp1 <= 0) tmp1 += n;

                if(tmp2 > n) tmp2 -= n;

                dp[1 - u][i] = 0.5 * dp[u][tmp1] + 0.5 * dp[u][tmp2];

            }

            u ^= 1;

        }

        double ans = 0;

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

            ans += dp[u][i];

        }

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

    }

    return 0;

}

秒客网

HDU - 4576 Robot（概率dp+滚动数组）

相关文章