首页 > 其他 > 详细

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

时间:2019-01-17 00:19:36      阅读:39      评论:0      收藏:0      [点我收藏+]

标签:lan   class   就是   com   ++   php   make   pair   for   

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2784

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

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

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

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mkp make_pair
#define fir first
#define sec second
#define db double
using namespace std;
const int N=35;
int n,m,w[N];db P;
pair<db,db> 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<db,db> 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;
}

 

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

标签:lan   class   就是   com   ++   php   make   pair   for   

原文:https://www.cnblogs.com/Narh/p/10280113.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号