题目链接:hdu 4576 Robot
题目大意:给出n,m,l,r表示有一个由n个位置组成的环,序号按照顺时针来是1~n。起始位置默认为1,现在走m步,给出m步的大小,对于每一步来说可以选择顺时针和逆时针移动,问说最后落在l~r这片区间的概率。
解题思路:dp[i][j]表示说第i步移动到j的概率,注意是概率,因为基数很大,所以不可能直接计算出来可能的种类。然后dp[i][j]的话,数组太大,所以用滚动数组优化空间。
#include <stdio.h>
#include <string.h>
const int N = 205;
double dp[2][N];
int n, m, l, r, t, w;
int main () {
while (scanf("%d%d%d%d", &n, &m, &l, &r) == 4 && n + m + l + r) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= m; i++) {
scanf("%d", &w);
int now = i&1;
int pre = !now;
for (int j = 0; j < n; j++) {
if (dp[pre][j] > 0) {
double val = dp[pre][j]*0.5;
dp[now][(j+w+n)%n] += val;
dp[now][(j-w+n)%n] += val;
}
dp[pre][j] = 0;
}
}
double ans = 0;
for (int i = l - 1; i < r; i++)
ans += dp[m&1][i];
printf("%.4lf\n", ans);
}
return 0;
}
分享到:
相关推荐
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
HDU的一题........HDU DP动态规
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
杭电OnlineJudge 200-2099的解题报告
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
acm hdu as easy as a+b
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1695 GCD(欧拉函数+容斥原理).docx
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163