ACdream 1113 The Arrow (概率dp求期望)

 

The Arrow

Time Limit: 2000/1000MS (Java/Others)
Memory Limit: 128000/64000KB (Java/Others)

Problem Description

The history shows that We need heroes in every dynasty. For example, Liangshan Heroes. People hope that these heroes can punish the bad guys and recover the justice. Nowadays, we also need heroes to provent us from being chopped, or being attacked by a bomb.

Kuangbin is a very very very very very.... (very * 1e9 ) good boy, after he knows The Arrow, he want to be The Arrow of China. But he is also a little afraid of being killed by the bad guys. So he decides to throw dices to make the decision.

The dice is a cube with 1 2 3 4 5 6 on it's sides. When he throws a dice, every number is of the same probablity to appear. He will write down a number N in the paper at first, and then throw the dice. When the sum of the number he throwed is less than N, he will keep throwing. But if the sum exceeds N, this throwing does not count.

For example, If the sum is 5,and N is 6, if we throw 2, 5 + 2 > 6, then the sum keeps to be 5.

If he can end the throwing in a certain time, he will make the decision to become The Arrow.

Now , kuangbin wonders that what's the expectation of the time of throwing dices.

Input

First line, The number of cases t <= 100

In the next t lines, there will be t numbers.

every number is not bigger than 100000

Output

Each test output a number rounded to the second digit.

Sample Input

1
1

Sample Output

6.00

Source

wuyiqi

Manager

wuyiqi

題目鏈接：http://acdream.info/problem?pid=1113

題目大意：擲骰子，如果之前擲到的點數和加當前擲到的點數大於n則不做處理，否則累加，求擲到數字n擲的次數的期望

題目分析：首先dp[n]肯定是0，往前推
得到dp[i] = cnt / 6dp[i] + 1/6dp[i - 1] + 1/6dp[i - 2] + ... + 1/6dp[i - 6] + 1，這裡cnt表示的是之前點數和加上當前點數大於n的當前點數的個數，化簡這個式子遞推dp[i]即可

#include 
#include 
int const MAXN = 1e5 + 5;
double dp[MAXN];

int main()
{
    int T, n;
    scanf(%d, &T);
    while(T--)
    {
        scanf(%d, &n);
        memset(dp, 0, sizeof(dp));
        dp[n] = 0.0;
        for(int i = n - 1; i >= 0; i--)
        {
            dp[i] = 0;
            int cnt = 0;
            for(int j = 1; j <= 6; j++)
            {
                if(i + j > n)
                    cnt ++;
                else
                    dp[i] += dp[i + j];
            }
            dp[i] += 6;
            dp[i] /= (6 - cnt);
        }
        printf(%.2f
, dp[0]);
    }
}