bzoj 2784 [JLOI2012]时间流逝——树上高斯消元-白红宇

bzoj 2784 [JLOI2012]时间流逝——树上高斯消元

阅读量：6991 次

发布时间：2019-06-27

本文共 895 字，大约阅读时间需要 2 分钟。

题目：

一个状态可以加很多个能量圈，但减少能量圈的情况只有一种。所以可以用树来刻画。

然后就变成树上高斯消元的套路了。注意根节点的 P 等于 0 。

发现不是要求 dp[ 1 ] 就必须在那个式子里设出 a*dp[ 1 ] 之类的。

据说树上的点大概有 1.2*10⁶ 个。大概就是贝尔数吧。

#include
     
      #include
      
       #include
       
        #define mkp make_pair#define fir first#define sec second#define db doubleusing namespace std;const int N=35;int n,m,w[N];db P;pair
        
          dfs(int lm,int s){  db ta=0,tb=0;if(s>n)return mkp(0,0);  for(int i=1;i<=lm;i++)    {      pair
         
           v=dfs(i,s+w[i]);      ta+=v.fir; tb+=v.sec;    }  if(!s)P=0;  ta=1-(1-P)/lm*ta; ta=1/ta;  tb=((1-P)/lm*tb+1)*ta; ta=P*ta;  return mkp(ta,tb);}int main(){  while(scanf("%lf",&P)==1)    {      scanf("%d%d",&n,&m);      for(int i=1;i<=m;i++)scanf("%d",&w[i]);      sort(w+1,w+m+1);//      printf("%.3f\n",dfs(m,0).sec);    }  return 0;}