ZOJ Problem Set - 3468 Dice War
飞机票: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4254
分析:其实这个题难懂的是题意啊~~~后来百度下骰子游戏菜知道这个题的意思。。先来看下骰子游戏的规则
规则略微有点复杂,刚开始可能不太明白,我详细解释下:
你的终极目标是占领所有的地块,你的颜色是紫色。
占领地块的方法就是用你的地块攻击相邻的地块,胜负由这两个地块上的骰子掷出点数决定。
1)如果你赢了,那么原来地块上的骰子变成一个,新占领地块上的骰子数 = 原来地块骰子数 - 1 ;
2)如果平了或者输了,那么你的地块上的骰子也会变成一个。
只要你的地块上的骰子数大于一个,就可以攻击别人。
在攻击结束时,点击 "End Turn" 可以补充兵力,补充的总数是你此时连在一起的地块的总数,分配则是随机的。每个地块上最多有 8 颗骰子。
提示策略:刚开始的时候尽量把自己的地都连到一起,中期的时候怎样布阵对于进攻和防守都很重要,后期基本都是八颗八颗的硬碰硬了 :P
看了应该就秒懂了吧。反正题目就是说给你攻击者的骰子数和防御者的骰子数。然后求攻击者赢得概率(就是说攻击者的点数严格大于防御者的点数)。。。这里要注意:如果攻击者的骰子数是1,那么就不能攻击,意思就是说赢得概率是0。。。然后你就可以根据概率来搞了。。。对于数学概率的渣渣,,,只有这么一个想法就是说把攻击者的点数枚举。。。怎么枚举法??
已知n,那么攻击者的点数就是在n~6*n之间。。。然后枚举每个点数所占的概率。。。就是 k的可能方法有几种/6^n就是k的概率、、然后你要赢:那么就是m~6*m之间小于k的概率 那么就是(m~k-1)之间所有可能的方法/6^m的概率、、、然后从将所有的相加就是答案。。。这里计数方法,我先是DFS。。。其实也不慢,但是也不快。。。后来想到了DP。。。就是按骰子数来DP,然后当前骰子有6中可能1~6,然后看前面的是否出现过k,出现过,那么当前(k+(1~6))就要累加了。。。这样复杂度就直接变为(6*n)^2
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <vector> #include <stack> #include <map> #define LL long long using namespace std; int ai[2][9][49]; int bi[2]; int p; void play() { if(bi[0]<=1) { printf("0\n"); return; } for(int z=0; z<=1; z++) { int e=6*bi[z]; memset(ai[z][0],0,sizeof(ai[z][0])); ai[z][0][0]=1; for(int j=1; j<=bi[z]; j++) { memset(ai[z][j],0,sizeof(ai[z][j])); for(int i=1; i<=6; i++) { for(int k=0; k<=e; k++) { if(ai[z][j-1][k]>0) { ai[z][j][k+i]+=ai[z][j-1][k]; } } } } } int fm=pow(6.0,bi[0]); int fm1=pow(6.0,bi[1]); for(int i=1; i<=6*max(bi[0],bi[1]); i++) { ai[1][bi[1]][i]=ai[1][bi[1]][i]+ai[1][bi[1]][i-1]; } double over=0; for(int i=1; i<=6*bi[0]; i++) { double pop=((double)(ai[0][bi[0]][i]))/fm; double pop1=((double)(ai[1][bi[1]][i-1]))/fm1; over=over+(pop*pop1); } printf("%.8lf\n",over); } int main() { while(scanf("%d%d",&bi[0],&bi[1])!=EOF) { play(); } return 0; }