原题链接：http://hihocoder.com/problemset/problem/1489

题意：
给定初始概率P%，增加概率Q%，要求的结果N
每次行动能成功得到宝物的概率是 ⌊P/(2^I)⌋，其中l是已经获得的宝物数，如果该次行动没有获取宝物，则概率在原基础上加上Q%（最多加到100%）
求获取N个宝物的期望行动数

样例输入
50 75 2
样例输出
3.25

设dp[i]是获得i个宝物的期望
分析如下：
若获得第i个宝物，则获得下一个的可能性如下：

• 下一次获得：⌊P/(2ⁱ)⌋
• 下下一次获得：⌊P/(2ⁱ)⌋+Q（在上面的状况不发生的情况下）
• ……
• j次后获得：⌊P/(2ⁱ)⌋+Q*j（在上面的状况不发生的情况下）

所以，dp[i] = dp[i-1] + sum{ p * ⌊P/(2<sup>i</sup>)⌋+Q*j *(1+j) }
其中，p是前面状况都不发生的概率。（注意Q做多能加到100%）

另外，取整这里要注意利用，2^8以上可以直接看错128，因为结果都是0

#include <cstdio>

const int maxn = 1e6 + 5;
const double eps = 1e-9;
double dp[maxn];

int pow(int m) {
    const int pow2[8] = {1, 2, 4, 8, 16, 32, 64, 128};
    m = m <= 8 ? m : 8;
    return pow2[m];
}

int main() {
    int P, Q, N;
    scanf("%d%d%d", &P, &Q, &N);

    dp[0] = 0;
    for (int i = 1; i <= N; ++i) {
        int thisP = P / pow(i - 1);

        double sum = 0;

        dp[i] = dp[i - 1];

        bool go = true;
        for (int j = 0; go && j <= 100; ++j) {
            int temp = (double)(thisP + j * Q);
            if (temp >= 100)
                temp = 100;
            double TEMP = (double)temp / 100;
            dp[i] += (1 - sum) * TEMP * (j + 1);
            sum += (1 - sum) * TEMP;

            if (temp == 100)
                go = false;
        }
    }

    printf("%.2f\n", dp[N]);
    return 0;
}