BZOJ 1076: [SCOI2008]奖励关(概率+dp)

首先嘛，看了这么久概率论真的不错啊。看到就知道怎么写（其实也挺容易的= =）

直接数位dp就行了

CODE：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int g[20],a[20],q[20];

double f[120][66000];

int main(){

int n,m;

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

for (int i=1;i<=n+1;i++) g[i]=1<<(i-1);

for (int i=1;i<=n;i++){

scanf("%d",&a[i]);

for (;;){

int x;

scanf("%d",&x);

if (x==0) break;

q[i]+=g[x];

}

}

for (int i=m;i;i–) {

for (int j=0;j<=g[n+1]-1;j++) {

f[i][j]=0;

for (int k=1;k<=n;k++) {

if ((j&q[k])==q[k]) f[i][j]+=max(f[i+1][j],f[i+1][j|g[k]]+a[k]);

else f[i][j]+=f[i+1][j];

}

f[i][j]/=n*1.0;

}

}

printf("%.6lf\n",f[1][0]);

return 0;

}