首页 > 代码库 > ZOJ 3329 - One Person Game
ZOJ 3329 - One Person Game
令f(i)为i分掷色子结束的次数期望，已知f(i|i>N) = 0，那么很容易得到：
因为初始状态是0分，所以答案就是f(0)。我们这里我们采取一个比网上题解更有趣的方法来解出这个式子：
令
，那么f(i) = ∑pkf(i+k) + A，我们把左右两端同时除以A，得到f(i)/A = ∑pkf(i+k)/A + 1
然后f(0) = ∑pkf(k) + A， 同时f(0) = (A-1)/p0， 通过整理，那么我们可以解出
，然后此时f(0)=(A-1)/p0。
要说编程上需要注意的地方就是不要用1.0f（主要是我手贱），即使是double类型！到时候挂的莫名其妙的还找不到错就悲剧了。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef double DB;DB dp[507], p[37];int N, maxk;DB f(int i){ if (i > N) return 0; if (~*(int *)&dp[i]) return dp[i]; dp[i] = 1; for(int k=1; k<=maxk; ++k) { if (i+k > N) break; dp[i] += p[k] * f(i+k); } return dp[i];}int main(void){ int T; scanf("%d", &T); for(int t = 1; t<=T; ++t) { int k1, k2, k3, a, b, c; scanf("%d%d%d%d%d%d%d", &N, &k1, &k2, &k3, &a, &b, &c); memset(dp, -1, sizeof dp); memset(p, 0, sizeof p); DB p0 = 1.0 / k1 / k2 / k3; for(int i=1; i<=k1; ++i) { for(int j=1; j<=k2; ++j) { for(int k=1; k<=k3; ++k) { if (i != a || j != b || k != c) p[i+j+k] += p0; } } } maxk = k1+k2+k3; DB s, u; s = u = k1*k2*k3; for(int k=1; k<=maxk; ++k) { if (k > N) break; u -= p[k] * f(k); } printf("%.15f\n", (s/(u-1) - 1)/p0); } return 0;}
| 2014-11-05 00:36:03 | Accepted | 3329 | C++ | 0 | 176 | esxgx |
ZOJ 3329 - One Person Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。