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

题目: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=;
int n,m,w[N];db P;
pair<db,db> dfs(int lm,int s)
{
db ta=,tb=;if(s>n)return mkp(,);
for(int i=;i<=lm;i++)
{
pair<db,db> v=dfs(i,s+w[i]);
ta+=v.fir; tb+=v.sec;
}
if(!s)P=;
ta=-(-P)/lm*ta; ta=/ta;
tb=((-P)/lm*tb+)*ta; ta=P*ta;
return mkp(ta,tb);
}
int main()
{
while(scanf("%lf",&P)==)
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d",&w[i]);
sort(w+,w+m+);//
printf("%.3f\n",dfs(m,).sec);
}
return ;
}
上一篇:windows全系列激活脚本-改良版.cmd


下一篇:android gps开发必备资料(含测试demo下载)