首页 > ACM题库 > HDU-杭电 > HDU 4074-Darts-概率-[解题报告]HOJ
2015
04-16

HDU 4074-Darts-概率-[解题报告]HOJ

Darts

问题描述 :

After a long week of work at the ICPC Headquarters, Bill and his friends usually go to a small pub on Friday evenings to have a couple of beers and play darts. All of them are well aware of the fact that their ability at darts decreases at the same rate as the amount of beer left in their mugs.
They always play 501, one of the easiest games. Players start with a score of N points (typically, N = 501, hence the name) and take turns throwing darts. The score of each player decreases by the value of the section hit by the dart, unless the score becomes negative, in which case it remains unchanged. The first player to reach a score of 0 wins. The figure below shows the dartboard with which the game is played.
Lights

As the clock ticks closer to midnight and they start running out of beer, everyone wonders the same: is it worth trying to aim the dart at a speci c section? Or is it better just to throw the dart at a random section on the dartboard? You are asked to deal with the question by finding out what would happen if two players (A and B) applying these two different strategies were to play against each other:

Player A throws the darts at random, and consequently they land with equal probability in each of the sections of the dartboard.
If Player B aims at a certain section, the dart has the same probability of landing in the correct one as in each of the two adjacent ones (the neighbouring regions to the left and right). Moreover, he is completely aware of his ability and sober enough to aim at the section that maximizes his probability of winning.

Given the initial score of both players, can you determine the probability that the first player wins? Of course, being the first to throw a dart might be advantageous, so the answer depends on who plays first.

输入:

The input consists of a series of lines, each containing an integer N (1<=N<=501), the initial score of both players. A case with N = 0 marks the end of the input and must not be processed.

输出:

The input consists of a series of lines, each containing an integer N (1<=N<=501), the initial score of both players. A case with N = 0 marks the end of the input and must not be processed.

样例输入:

5
100
0

样例输出:

0.136363636364 0.909090909091
0.072504908290 0.950215081962

题目大意:

就是现在两个人A和B进行飞镖游戏,现在A每次都是随意地向标靶投掷非标,击中不同得分区域的概率都是1/20, B每次都会选择瞄准使得自己赢的可能性最大的那块区域进行投掷,当他瞄准一块区域时,有1/3的几率击中瞄准的区域,另外分别有1/3和1/3的概率击中瞄准区域的左边或者右边的区域,现在给出一个整数n,1 <= n <= 501表示现在A和B的剩余分数都是n, 现在两个人进行投掷,当投到分数为 k 的区域时,如果当前分数大于等于k,就减去k分,否则分数不变,分数最先到达0的人获胜。

要求分别求出A先手时A获胜的概率和B先手时B获胜的概率。

大致思路:

用Pa(n , m)表示当A剩余n分,B剩余m分时,A先手获胜的概率

用Pb(n, m)表示当A剩余n分, B剩余m分时,B先手获胜的概率

那么当n和m都不小于20的时候有递推式:

Darts

当n或者m小于20时,上式中可能出现减去d[i]不够的情况,根据游戏规则将会形成环,这样子的话由于题目要求精确到小数点后一定位数即可,所以可以取一个适当的循环次数来得到相对精确的值。

代码如下:

Result  :  Accepted     Memory  :  4212 KB     Time : 796 ms

/*
 * Author: Gatevin
 * Created Time:  2014/8/24 11:54:43
 * File Name: hehe.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

#define maxn 501

int n;
double dpA[maxn + 1][maxn + 1];
double dpB[maxn + 1][maxn + 1];

int d[] = {20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5};

int loop = 0;

int main()
{
    memset(dpA, 0, sizeof(dpA));
    memset(dpB, 0, sizeof(dpB));
    for(int i = 1; i <= maxn; i++)
    {
        dpA[0][i] = 1;
        dpB[i][0] = 1;
    }
    for(int i = 1; i <= maxn; i++)
    {
        for(int j = 1; j <= maxn; j++)
        {
            loop = 0;
            do
            {
                double a = 0;
                for(int k = 0; k < 20; k++)
                {
                    if(i >= d[k])
                        a += dpB[i - d[k]][j];
                    else
                        a += dpB[i][j];
                }
                dpA[i][j] = 1 - a / 20.;
                a = 0;
                for(int h = 0; h < 20; h++)
                {
                    double b = 0;
                    for(int k = -1; k <= 1; k++)
                    {
                        int tmp = (h + 20 + k) % 20;
                        if(j >= d[tmp])
                            b += dpA[i][j - d[tmp]];
                        else
                            b += dpA[i][j];
                    }
                    b = 1 - b / 3.;
                    a = max(a, b);
                }
                dpB[i][j] = a;
                loop++;
            }
            while((i < 20 || j < 20) && loop <= 70);
        }
    }
    while(scanf("%d", &n), n)
        printf("%.12f %.12f\n", dpA[n][n], dpB[n][n]);
    return 0;
}

loop次数去太大会超时
如果打表的话交个16000+B的代码也是可以的….

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/gatevin/article/details/38803897