题意
抄袭自https://www.cnblogs.com/paul-guderian/p/7624039.html
多组输入n,m,l,r。表示在一个环上有n个格子。接下来输入m个w表示连续的一段命令,每个w表示机器人沿顺时针或者逆时针方向前进w格,已知机器人是从1号点出发的,输出最后机器人停在环上[l,r]区间的概率。n(1≤n≤200) ,m(0≤m≤1,000,000)。
sol
无脑概率dp
$f[i][j]$表示第$i$轮,在$j$位置的概率
转移的时候枚举下一轮往哪儿走
最后把$(l, r)$内的加起来即可
#include<cstdio> #include<cstring> using namespace std; const int maxn = 201; int n, m, l, r; double f[2][maxn]; int get(int x) { if(x <= 0) x += n; if(x > n) x -= n; return x; } int main() { while(scanf("%d %d %d %d", &n, &m, &l, &r)) { memset(f, 0, sizeof(f)); if(!n && !m && !l && !r) break; int o = 0; f[o][1] = 1; for(int i = 1; i <= m; i++) { o ^= 1; int x; scanf("%d", &x); x %= n; for(int j = 1; j <= n; j++) f[o][j] = (f[o ^ 1][get(j - x)] + f[o ^ 1][get(j + x)]) / 2; } double ans = 0; for(int i = l; i <= r; i++) ans += f[o][i]; printf("%.4lfn", ans); } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/608398.html