[Codeforces-div.1 167B] Wizards and Huge Prize

试题分析

注意到每个物品互相独立，互不干扰之后就非常好做了。

算出一个物品最后的价值期望，然后乘以K即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline int read(){

    int x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const int INF = 2147483600;

const int MAXN = 100010;

int N,K; double f[2][MAXN+1];

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    N=read(),K=read();

    //for(int j=1;j<=N+1;j++) f[N&1][j]=0;

    for(int i=N-1;i>=0;i--){

        int x=(i&1),y=(x^1);

        //for(int j=1;j<=N;j++) f[x][j]=0;

        for(int j=1;j<800;j++)

            f[x][j]=(f[y][j+1]+j)/(1.0*K*(j+1))+

                    1.0*j*(f[y][j]+(1.0*(j+1)/2.0))/(1.0*K*(j+1))+

                    (1.0-(1.0/(1.0*K)))*f[y][j];

    } //cout<<f[0][1]<<endl;

    printf("%.9lf",1.0*K*f[0][1]);

    return 0;

}

巴特西

[Codeforces-div.1 167B] Wizards and Huge Prize

[Codeforces-div.1 167B] Wizards and Huge Prize

试题分析

最新文章

热门文章