来自lyd课件

发现s和last(s),next(s)成树结构，然后把式子化简成kx+b的形式，做树形dp即可

#include
    
     #include
     
      #include
      
       using namespace std;int n,t,a[105];double p,q;struct qwe{    double k,b;    qwe(double K=0,double B=0)    {        k=K,b=B;    }};qwe dfs(int s,int mx){    if(s>t)         return qwe(0,0);        double ne,b=0,k=0,r=1;    ne=1.0/(double)mx;    for(int i=1;i<=mx;i++)    {        qwe nw=dfs(s+a[i],i);        b=b+nw.b,k=k+nw.k;    }    q=s?p:0.0;    r=1.0-(1.0-q)*ne*k;    k=q/r;    b=((1.0-q)*ne*b+1)/r;    return qwe(k,b);}int main(){    while(~scanf("%lf%d%d",&p,&t,&n))    {        for(int i=1;i<=n;i++)             scanf("%d",&a[i]);        sort(a+1,a+n+1);        printf("%.3lf\n",dfs(0,n).b);    }    return 0;}