NC20132. [JLOI2012]时间流逝
描述
输入描述
输入包含多个测例。对每个测例会有两行。
第一行是一个浮点数P，一个整数T和一个整数N。P是每天遇到果冻鱼的概率，T是阈值。
第二行是N个不同的正整数，表示每一种能量圈的能量值。
输出描述
对于每个测例，输出一行表示预计要过多少天你的能量值能够超过阈值，四舍五入到三位小数。
示例1
输入:
0.5 0 1 1 0.5 1 2 1 2
输出:
1.000 2.000
C++11(clang++ 3.9) 解法, 执行用时: 26ms, 内存消耗: 496K, 提交时间: 2020-03-28 14:36:34
#include<bits/stdc++.h>
using namespace std;
double p;
int T,n;
int a[100];
pair<double,double> dfs(int sum,int lim)
{
if(sum>T) return make_pair(0,0);
double P1=sum?p:0.0;
double k=0.0,b=0.0,A=(1-P1)/lim;
for(int i=1;i<=lim;i++)
{
auto tmp=dfs(sum+a[i],i);
k+=tmp.first;b+=tmp.second;
}
return make_pair(P1/(1-A*k),(1+A*b)/(1-A*k));
}
int main()
{
while(cin>>p>>T>>n)
{
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
printf("%.3f\n",dfs(0,n).second);
}
return 0;
}