一开始想了一个很沙雕思路，是dp嵌套，先线性dp处理出每个人的必须入队的捆绑人之和（战斗力和代价），然后接着线性dp处理出最优的解，但发现算法假的，因为这个东西没有无后效果性。因为可能一个分子分母都很大的情况下比值很大，而另外一种情况是分子分母很小比值一样很大但是比前面那个小，这样小的被舍掉了。可是现在有一个比较小的捆绑人，加入到之前那个分子小的得到的比值会比加入那个大的要大。这样算法死了。
然后紧接着想到了01分数规划（我还没打过题呢），因为这个形式真的很想，上下分子分母，可以小数二分答案，精度卡的又不是很死，唯一的问题就是捆绑人问题，我不能把它们分开，但是不分开又会算重，所以用树上背包来验证即可。
但是要注意的是并不是取最大值而是取装满了的最大值，就是说装的是负数也要装入背包。这样在背包的一开始赋初值的时候直接赋上这个节点的物品，相当于强制购买。然后因为2500的数据要跑子树归并，瞎写一下就好了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 const int maxn=2505,INF=1e9; 7 int n,K,mx,a[maxn],b[maxn],sz[maxn],r[maxn],d[maxn]; 8 double c[maxn],dp[maxn][maxn],tmp[maxn]; 9 vector<int> ch[maxn]; 10 void dfs(int x) 11 { 12 for(int i=0;i<ch[x].size();i++) dfs(ch[x][i]); 13 sz[x]=1;dp[x][1]=c[x]; 14 for(int i=0;i<ch[x].size();i++) 15 { 16 int t=ch[x][i]; 17 for(int j=0;j<=K;j++) tmp[j]=-INF; 18 for(int j=0;j<=min(sz[x],K);j++) 19 for(int k=0;k<=min(sz[t],K-j);k++) 20 tmp[j+k]=max(dp[x][j]+dp[t][k],tmp[j+k]); 21 sz[x]+=sz[t]; 22 for(int j=0;j<=min(sz[x],K);j++) dp[x][j]=max(tmp[j],dp[x][j]); 23 } 24 } 25 bool check(double mid) 26 { 27 for(int i=0;i<=n;i++) 28 { 29 c[i]=1.0*a[i]-mid*b[i]; 30 for(int j=0;j<=K;j++) dp[i][j]=-INF; 31 } 32 dfs(0); 33 return dp[0][K]>=0; 34 } 35 int main() 36 { 37 scanf("%d%d",&K,&n);K++; 38 for(int i=1;i<=n;i++) 39 { 40 scanf("%d%d%d",&b[i],&a[i],&r[i]); 41 mx+=a[i]; 42 ch[r[i]].push_back(i); 43 } 44 double l=0,r=1e7; 45 while(r-l>1e-4) 46 { 47 double mid=(l+r)/2; 48 if(check(mid)) l=mid; 49 else r=mid; 50 } 51 printf("%.3lf ",l); 52 return 0; 53 }