【Codeforces 698C】LRU

题目传送门：http://codeforces.com/problemset/problem/698/C

这个题目嘛，貌似第一眼都会想到状压？然后内存就爆炸了。
比赛的时候果断弃疗…….

不过，这道题真的出得很好欸！做了以后有一种神清气爽的感觉！o(*￣▽￣*)ブ
具体来说，就是倒着来考虑：一个一个往里加，直到装满
详见官方题解：http://codeforces.com/blog/entry/46148

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

const int MAXN = 2000000;
const double EPS = 1e-12;

int n,k,cnt[MAXN],tot;
double f[MAXN],p[MAXN],vout[MAXN],mst[MAXN];

int main(){
	cin>>n>>k; f[0] = 1; mst[0] = 1;
	for (int i=1;i<=n;i++) {cin>>p[i]; if (p[i] > EPS) tot++;} tot = min(tot, k);
	for (int i=1,lim=1<<n;i<lim;i++) cnt[i] = __builtin_popcount(i);
	for (int i=0,lim=1<<n;i<lim;i++) if (cnt[i] < k) for (int j=1;j<=n;j++) 
		if ((i & (1<<(j-1))) == 0) f[i|(1<<(j-1))] += f[i]*p[j]/mst[i], mst[i|(1<<(j-1))] = mst[i] - p[j];
	for (int i=1,lim=1<<n;i<lim;i++) if (cnt[i] == tot && f[i] > EPS) 
		for (int j=1;j<=n;j++) if (i & (1<<(j-1))) vout[j] += f[i];
	for (int i=1;i<=n;i++) printf("%.16lf ",vout[i]);
	return 0;
}