【CodeForces】698 C. LRU

【题目】C. LRU

【题意】给定空间为k的背包和n个物品，每次每个物品有pi的概率加入(Σpi=1)，加入时若发现背包中已有该物品则不改变，若背包满k个物品后再加入新物品则弹出最早加入的物品，求加入10^100次后每个物品在背包中的概率。n,k<=20

【算法】概率DP

【题解】进行10^100次加入后背包一定是满的且是最后加入的k个物品，所以问题转化为在空背包中加入物品至满，各个物品在背包中的概率。

设$f_S$表示背包中的物品状态为S的概率，最后只需要统计所有恰好k个1的状态对物品的贡献即可。

根据全概率公式，P(A)=ΣP(B_i)*P(A|B_i)，有：

f[S]=Σf[S-2^(j-1)]*p[j]+f[S]*Σp[j]，S&2^(j-1)=1

移项得f[S]=Σf[S-2^(j-1)]*p[j]/sum(S)，其中sum(S)是状态S中为0的物品的概率之和。

注意，当状态S为答案状态(k)时，统计不应该除以sum(S)，因为已满之后就不填了。

★特别注意，当物品中不满k件概率不为0时，背包容量应降为概率不为0的物品件数。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=,maxN=;

int n,k;

double p[maxn],f[maxN],ans[maxn];

int main(){

    scanf("%d%d",&n,&k);

    int cnt=n;

    for(int i=;i<=n;i++)scanf("%lf",&p[i]),cnt-=p[i]<1e-?:;

    k=min(cnt,k);//

    f[]=;

    for(int S=;S<(<<n);S++){

        f[S]=;

        int num=;double sum=;

        for(int i=;i<n;i++)if(S&(<<i))num++;else sum+=p[i+];

        if(num>k)continue;

        for(int i=;i<n;i++)if(S&(<<i)){

            f[S]+=f[S-(<<i)]*p[i+];

        }

        if(num==k){

            for(int i=;i<n;i++)if(S&(<<i))ans[i+]+=f[S];

        }

        f[S]/=sum;//

    }

    for(int i=;i<=n;i++)printf("%.10lf ",ans[i]);

    return ;

}

巴特西

【CodeForces】698 C. LRU

最新文章

热门文章