Description
JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。方便起见，JYY的编号是0号。每个候选人都由一位
编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。为了保证团队的和谐，JYY需要保证，
如果招募了候选人i，那么候选人Ri"也一定需要在团队中。当然了，JYY自己总是在团队里的。每一个候选人都有
一个战斗值Pi"，也有一个招募费用Si"。JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。
也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。
Input
输入一行包含两个正整数K和N。
接下来N行，其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用，战斗值和推荐人编号。
对于100%的数据满足1≤K≤N≤2500,0<"Si,Pi"≤10^4,0≤Ri<i
Output
输出一行一个实数，表示最佳比值。答案保留三位小数。
Sample Input
1 2
1000 1 0
1 1000 1
1000 1 0
1 1000 1
Sample Output
0.001
题目传送门
这道垃圾题。。。我tm调了一天。。TLE到吐
一眼01分数规划，然后二分。。最后树形DP
然后。。有个丧病的家伙卡掉了我的做法。。。。
以后再填吧
大家帮忙看一下TLE代码，该怎么改进
多谢！
代码如下：
#include<cmath>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define eps 1e-4#define INF 1<<25using namespace std;struct node{ ???int x,y,next;}a[4100000];int len,last[4100000];void ins(int x,int y){ ???len++; ???a[len].x=x;a[len].y=y; ???a[len].next=last[x];last[x]=len;}int n,m;double tot[2510],cost[2510];int d[2510];double f[2510][2510];int mem[2510];void treedp(int x,double C){ ???f[x][0]=0.0; ???f[x][1]=tot[x]-C*cost[x];mem[x]=1; ???for(int k=last[x];k;k=a[k].next) ???{ ???????int y=a[k].y; ???????treedp(y,C); ???????for(int i=m;i>1;i--) ???????????for(int j=0;j<=mem[y];j++) ???????????{ ???????????????if(i-j>=1) ???????????????????f[x][i]=max(f[x][i],f[y][j]+f[x][i-j]); ???????????????else break; ???????????} ???????????????????????mem[x]+=mem[y]; ???}}bool check(double C){ ???memset(mem,0,sizeof(mem)); ???memset(f,-INF,sizeof(f)); ???treedp(0,C); ???if(f[0][m]>=0.0)return true; ???return false;}int main(){ ???freopen("a.in","r",stdin); ???freopen("a.out","w",stdout); ???scanf("%d%d",&m,&n);len=0; ???for(int i=1;i<=n;i++) ???{ ??????????scanf("%lf%lf%d",&cost[i],&tot[i],&d[i]); ??????????ins(d[i],i); ???} ???double l=0.0,r=3.0; ???double mid,ans=0.0; ????while(l<r) ???{ ???????mid=(l+r)/2; ???????if(check(mid)==true){ans=mid,l=mid+eps;} ???????else r=mid-eps; ???} ???printf("%.3lf\n",ans); ???return 0; ???}by_lmy
BZOJ4753: [Jsoi2016]最佳团体
原文地址：https://www.cnblogs.com/MT-LI/p/8570160.html