HDU 4576 （2013杭州邀请赛J题-dp滚动数组优化）

本文主要是介绍HDU 4576 （2013杭州邀请赛J题-dp滚动数组优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4576

题意：1-n的环，现在m次操作，每次顺时针或逆时针走w步，顺逆概率相同，问最后走完落在[l,r]内的概率是多少。

思路：dp，由于m很大，要滚动数组优化，dp[i][j]代表i步走到j这个位置的概率，那么只可能由i - 1步顺时针或逆时针到达，状态转移挺好想的。

主要是，这题卡时间也是卡得厉害，有点坑。

代码：

#include <stdio.h>
#include <string.h>const int N = 205;
int n, m, l, r, w, i, j, pre, now;
double dp[2][N];int main() {while (~scanf("%d%d%d%d", &n, &m, &l, &r) && n || m || l || r) {memset(dp, 0, sizeof(dp));dp[0][0] = 1;for (i = 1; i <= m; i++) {scanf("%d", &w);now = i&1;pre = !now;for (j = 0; j < n; j++) {if (dp[pre][j] == 0) continue;//不加超时dp[now][(j + w) % n] += 0.5 * dp[pre][j];dp[now][(j - w + n) % n] += 0.5 * dp[pre][j];dp[pre][j] = 0;}}double ans = 0;for (i = l - 1; i < r; i++)ans += dp[m&1][i];printf("%.4lf\n", ans);}return 0;
}

这篇关于HDU 4576 （2013杭州邀请赛J题-dp滚动数组优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---