Codeforces Round #363 (Div. 1) C. LRU

题意:

n个数,长度为k的缓存,每次询问,每个数以pi的概率被选,如果不在缓存区则加入,如果缓存区满了,则第一个进缓存的出来,问10^100次询问以后每个数在缓存的概率

思路:

状压DP,看了hzwer的代码

f[x]表示当前状态为x的概率

枚举不在缓存区的数:f[t]+=f[x]*(p[i]/tot);  t=x|(1<<(i-1)); tot是当前状态情况下,不在缓存区的所有概率

如果缓存区数大于k,则当前状态概率为0

 // #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = 2e5+;
const int M = 1e6+;
const int MOD = 1e9+;
#define LL long long
#define LB long double
#define mi() (l+r)>>1
double const pi = acos(-);
const double eps = 1e-;
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
int n,k;
LB p[],ans[],f[<<];
LB dp(int x){
if(x==) f[x]=;
LB tot=;
int cnt=;
for(int i=;i<=n;i++){
if((x&(<<(i-)))==) tot+=p[i];
else cnt++;
}
if(cnt>=k){
if(cnt>k) return ;
for(int i=;i<=n;i++){
if(x&(<<(i-))) ans[i]+=f[x];
}
return f[x];
}
for(int i=;i<=n;i++){
if((x&(<<(i-)))==){
int t=x|(<<(i-));
f[t]+=f[x]*(p[i]/tot);
}
}
return f[x];
}
int main(){
// fre();
scanf("%d%d",&n,&k);
int m=n;
for(int i=;i<=n;i++){
cin>>p[i];
if(p[i]<=1e-)
m--;
}
k=min(m,k);
for(int i=;i<(<<n);i++) dp(i);
for(int i=;i<=n;i++) printf("%.9lf ",(double)ans[i]);
return ;
}
上一篇:JSP页面静态化总结之一使用URLRewrite实现url地址伪静态化


下一篇:SQL大数据操作统计