https://projecteuler.net/problem=503

const int N = int(1e6) + 9;

int n = 1000000;

DB f[N];



// randomly choosing i elements from n elements,

// the expectation of the j-th element.

DB e(int i, int j){

    return (DB)(n+1) / (i+1) * j;

}



int main(){

    

#ifndef ONLINE_JUDGE

    freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);

    //freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);

#endif

    

    f[n] = (n + 1.0) / 2;

    int up = n - 1;

    DWN(i, n, 1){

        // in i-th round, we get j-th,

        // we enumerate the cut-off point: k,

        // that is, if j <= k, we stop.

        f[i] = f[i + 1]; // if k=0

        DB prob = 1, expe = 0;

        // the prob we don't stop ..

        // the expe if we stop.

        REP_1_C(k, up){

            expe += 1.0 / i * e(i, k); if (expe >= f[i]) break;

            prob -= 1.0 / i;

            if (expe + prob * f[i+1] < f[i]){

                f[i] = expe + prob * f[i+1];

                up = k;

            }

        }

    }

    printf("%.10f\n", f[1]);

}


// 3.8694550145

Posted by xiaodao
Category: PE