题目链接

GCJ 2008 APAC Semifinal C. Millionaire

思路

$$ \begin{aligned}这题的关键是离散化，按轮考虑\\\\dp[i][j] 表示第i轮第j个区间到百万目标的概率\end{aligned} $$

时间复杂度

$$ O(M4^{M}) $$

代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1 << 18;

double dp[2][MAXN];

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    for (int kase = 1; kase <= T; kase++) {
        int m, x;
        double p;
        scanf("%d", &m);// don't forget &
        scanf("%lf", &p);// don't forget &
        scanf("%d", &x);// don't forget &
        int n = 1 << m;
        for (int i = 0; i <= n; i++) {
            dp[0][i] = dp[0][1] = 0;
        }
        dp[0][n] = 1.0;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                double t = 0;
                int u = min(j, n - j);
                for (int k = 0; k <= u; k++) {
                    t = max(t, p * dp[(i - 1) & 1][j + k] + (1 - p) * dp[(i - 1) & 1][j - k]);
                }
                dp[i & 1][j] = t;
            }
        }
        int cur = 1LL * x * n / 1000000;
        printf("Case #%d: %.6f\n", kase, dp[m & 1][cur]);
    }
    return 0;
}