hdu 4576 Robot
1265 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=4576
暴力確率DP
暴力確率DP
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <iostream>
#include <cmath>
using namespace std;
#ifdef __GNUC__
#define ll long long
#else
#define ll __int64
#endif
const int MAXN = 205;
double dp[2][MAXN];
int main()
{
#ifdef __GNUC__
freopen("in.txt", "r", stdin);
#endif
int n, m, l, r;
int k;
int i;
while (scanf("%d%d%d%d", &n, &m, &l, &r) != EOF && (n+m+l+r))
{
int cur = 0;
dp[0][0] = 1.0;
for (i = 1; i < n; ++i)
{
dp[0][i] = 0.0;
}
while (m--)
{
scanf("%d", &k);
for (int j = 0; j< n; ++j)
{
dp[cur^1][j] = 0.5 * dp[cur][(j+k)%n] + 0.5 * dp[cur][(j-k+n)%n];
}
cur ^= 1;
}
double res = 0.0;
for (i = l-1; i< r; ++i)
{
res += dp[cur][i];
}
printf ("%.4lf
", res);
}
return 0;
}