hihocoder 1489.Legendary Items
visibility 37
微软2017年预科生计划在线编程笔试
原题链接:http://hihocoder.com/problemset/problem/1489

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

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


dp[i]是获得i个宝物的期望
分析如下:
若获得第i个宝物,则获得下一个的可能性如下:
  • 下一次获得:⌊P/(2i)⌋
  • 下下一次获得:⌊P/(2i)⌋+Q(在上面的状况不发生的情况下)
  • ……
  • j次后获得:⌊P/(2i)⌋+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;
}


评论
email
点击查看/关闭被识别为广告的评论

#