HDU 4576 Robot (概率DP)

时间:2024-01-06 19:42:38

暴力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;
}