首页 > ACM题库 > HDU-杭电 > hdu 2533 Mine-动态规划-[解题报告]C++
2014
02-09

hdu 2533 Mine-动态规划-[解题报告]C++

Mine

问题描述 :

在电子科大沙河校区的学生内网“风中论坛”中,有一种名叫“踩地雷”的游戏,游戏规则如下:

1.玩家在0到9中任意选择一个数字,并押上一定的赌金。
2.地雷号码由每日发贴排行榜产生,将上榜的N名会员的当日发帖量的最后一位加起来,得到的数字的十位和个位就是地雷号码,称为“大雷”,它们加起来余10也是地雷号码,称为“小雷”。
3.如果两个大雷不相同,则选择的数字不是这3个雷号之一的玩家净赢1倍赌金。
4.如果两个大雷不相同,而且其中没有0,则选择的数字是大雷的玩家净输3倍赌金,选择的数字是小雷的玩家净输2倍赌金。
5.如果两个大雷不相同,而且其中有0,则选择的数字是大雷(包括0)的玩家净输4倍赌金。
6.如果两个大雷相同,则选择的数字不是大雷或者小雷的玩家净输1倍赌金。
7.如果两个大雷相同,而且不是0,则选择的数字是大雷的玩家净赢3倍赌金,选择的数字是小雷的玩家净赢2倍赌金。
8.如果两个大雷相同,而且是0,则选择的数字是0的玩家净赢4倍赌金。
现在假设所有上榜的会员当日发帖量的最后一位是0到9中每个数字的概率都是1/10,给定N,求玩家压在每个数字上期望上能得到多少倍赌金的净收益。

输入:

输入包含多组数据。每组数据只有1个整数N(1<=N<=1000),N=0表示输入结束。

输出:

输入包含多组数据。每组数据只有1个整数N(1<=N<=1000),N=0表示输入结束。

样例输入:

1
0

样例输出:

-3.20 0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.30
#include<stdio.h>

double dp[1001][101];

int initDP(int w)
{
    int i;
    for(i = 0; i < 100; i ++)
    {
        dp[w][i] = 0;
    }
    return 0;
}

int init()
{
    int i, j, k;
    initDP(0);
    dp[0][0] = 1;
    for(i = 1; i <= 1000; i ++)
    {
        initDP(i);
        for(j = 0; j <= 9; j ++)
        {
            for(k = 0; k < 100; k ++)
            {
                dp[i][(k + j) % 100] += dp[i - 1][k] / 10;
            }
        }
    }
    return 0;
}

int get(int big1, int big2, int small, int x)
{
    if(big1 != big2)
    {
        if(x != big1 && x != big2 && x != small)
            return 1;
        if(big1 != 0 && big2 != 0)
        {
            if(x == big1 || x == big2)
                return -3;
            if(x == small)
                return -2;
        }
        if(big1 == 0 || big2 == 0)
        {
            if(x == big1 || x == big2)
                return -4;
        }
    }
    else
    {
        if(x != big1 && x != big2 && x != small)
            return -1;
        if(big1 != 0)
        {
            if(x == big1)
                return 3;
            if(x == small)
                return 2;
        }
        if(big1 == 0)
        {
            if(x == 0)
                return 4;
        }
    }
    return -1;
}

int main()
{
    int i, j, n;
    double result;
    init();
    while(scanf("%d", &n) != EOF && n != 0)
    {

        for(i = 0; i <= 9; i ++)
        {
            result = 0;
            for(j = 0; j < 100; j ++)
            {
                result += get(j % 10, j / 10, (j % 10 + j / 10) % 10, i) * dp[n][j];
            }
            if(i != 0)
                printf(" ");
            printf("%.2lf", result);
        }
        printf("\n");
    }
    return 0;
}

 

 


,
  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge