Chieh's Blog

Because Of Coding

ZOJ Problem Set - 3468 Dice War

Chieh posted @ 2015年1月06日 13:36 in ZOJ , 223 阅读

飞机票: 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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter