POJ-1644 To Bet or Not To Bet(概率DP)

To Bet or Not To Bet Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 1668 Accepted: 541 Description

Alexander Charles McMillan loves to gamble, and during his last trip to the casino he ran across a new game. It is played on a linear sequence of squares as shown below.

A chip is initially placed on the Start square. The player then tries to move the chip to the End square through a series of turns, at which point the game ends. In each turn a coin is fl ipped: if the coin is heads the chip is moved one square to the right and if the coin is tails the chip is moved two squares to the right (unless the chip is one square away from the End square, in which case it just moves to the End square). At that point, any instruction on the square the coin lands on must be followed. Each instruction is one of the following: 1. Move right n squares (where n is some positive integer) 2. Move left n squares (where n is some positive integer) 3. Lose a turn 4. No instruction After following the instruction, the turn ends and a new one begins. Note that the chip only follows the instruction on the square it lands on after the coin flip. If, for example, the chip lands on a square that instructs it to move 3 spaces to the left, the move is made, but the instruction on the resulting square is ignored and the turn ends. Gambling for this game proceeds as follows: given a board layout and an integer T, you must wager whether or not you think the game will end within T turns. After losing his shirt and several other articles of clothing, Alexander has decided he needs professional help-not in beating his gambling addiction, but in writing a program to help decide how to bet in this game. Input

Input will consist of multiple problem instances. The first line will consist of an integer n indicating the number of problem instances. Each instance will consist of two lines: the first will contain two integers m and T (1 <= m <= 50, 1 <= T <= 40), where m is the size of the board excluding the Start and End squares, and T is the target number of turns. The next line will contain instructions for each of the m interior squares on the board. Instructions for the squares will be separated by a single space, and a square instruction will be one of the following: +n, -n, L or 0 (the digit zero). The first indicates a right move of n squares, the second a left move of n squares, the third a lose-a-turn square, and the fourth indicates no instruction for the square. No right or left move will ever move you off the board. Output

Output for each problem instance will consist of one line, either Bet for. x.xxxx if you think that there is a greater than 50% chance that the game will end in T or fewer turns, or Bet against. x.xxxx if you think there is a less than 50% chance that the game will end in T or fewer turns, or Push. 0.5000 otherwise, where x.xxxx is the probability of the game ending in T or fewer turns rounded to 4 decimal places. (Note that due to rounding the calculated probability for display, a probability of 0.5000 may appear after the Bet for. or Bet against. message.) Sample Input

5 4 4 0 0 0 0 3 3 0 -1 L 3 4 0 -1 L 3 5 0 -1 L 10 20 +1 0 0 -1 L L 0 +3 -7 0 Sample Output

Bet for. 0.9375 Bet against. 0.0000 Push. 0.5000 Bet for. 0.7500 Bet for. 0.8954

概率DP题目, 递推即可,

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <string>

using namespace std;
#define MAX 999999
char a[55];
int m,t;
double dp[55][55];
int b[55];
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(dp,0,sizeof(dp));
        memset(b,0,sizeof(b));
        scanf("%d%d",&m,&t);
        for(int i=1;i<=m;i++)
        {
            scanf("%s",a);

             if(a[0]=='L')
                b[i]=MAX;
             else
                 sscanf(a,"%d",&b[i]);
        }
        b[0]=0;b[m+1]=0;b[m+2]=-1;
        dp[0][0]=1.0;
        for(int i=0;i<t;i++)
        {
            for(int j=0;j<m+1;j++)
            {
                if(b[j+1]==MAX)
                    dp[i+2][j+1]+=dp[i][j]*0.5;
                else
                    dp[i+1][j+b[j+1]+1]+=dp[i][j]*0.5;
                if(b[j+2]==MAX)
                    dp[i+2][j+2]+=dp[i][j]*0.5;
                else
                    dp[i+1][j+b[j+2]+2]+=dp[i][j]*0.5;
            }
        }
        double ans=0;
        for(int i=0;i<=t;i++)
            ans+=dp[i][m+1];
        if(ans>0.5)
            printf("Bet for. %.4f\n",ans);
        else if(ans==0.5)
            printf("Push. 0.5000\n");
        else if(ans<0.5)
            printf("Bet against. %.4f\n",ans);

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术小黑屋

Build Android Packages From Command Line

A few months ago,I dealed with a task:To build a large amount of apk files. The...

1273
来自专栏ml

HDUOJ------2492Ping pong

Ping pong Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

3357
来自专栏ml

HDU----(4291)A Short problem(快速矩阵幂)

A Short problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

3516
来自专栏小樱的经验随笔

HDU 2504 又见GCD(最大公约数与最小公倍数变形题)

又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2913
来自专栏大数据学习笔记

Hadoop基础教程-第9章 HA高可用(9.3 HDFS 高可用运行)(草稿)

第9章 HA高可用 9.3 HDFS 高可用运行 9.3.1 HA节点规划 节点 IP Zookeeper NameNode JournalNode Da...

2785
来自专栏ml

HDUOJ---hello Kiki

Hello Kiki Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K...

2819
来自专栏ml

hdu 1695 GCD(莫比乌斯反演)

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

4056
来自专栏Golang语言社区

在GO中编写一个简单的shell

In this post, we will write a minimalistic shell for UNIX(-like) operating syste...

1405
来自专栏ml

HDUOJ----2952Counting Sheep

Counting Sheep Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

3457
来自专栏ml

HDUOJ-------2493Timer(数学 2008北京现场赛H题)

Timer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2684

扫码关注云+社区

领取腾讯云代金券