题解 P4322 【[JSOI2016]最佳团体】

提供一种比较简单的dp方式。 首先，问题所求的明显是一种带除法最优化问题，可以利用分数规划规避除法。那么就剩下了树形依赖背包了。 明显可以直接在树上做背包，暴力是$O(n^3)$的。接下来可以考虑在树上优化，或者转成$dfs$序列并在上面$dp$。 具体来说，转移有: $Chkmax(dp[i+1][j+1],dp[i][j])$ $Chkmax(dp[nx[i]][j],dp[i][j])$ 其中$nx[i]$表示下一棵子树的$dfn$，$Chkmax(a,b)$表示$a=a>b?a:b$。 这样就是$O(n^2)$的了。加上分数规划，总时间复杂度为$O(n^2log ans)$。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) #define Chkmax(a,b) a=a>b?a:b template<typename T>inline void read(T &x) { T f=1;x=0;char c; for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=x*10+(c^48); x*=f; } using namespace std; void file() { #ifndef ONLINE_JUDGE freopen("luogu4322.in","r",stdin); freopen("luogu4322.out","w",stdout); #endif } const int MAXN=2517; static int n,m,s[MAXN],p[MAXN]; static vector<int>ed[MAXN]; inline void init() { read(m);read(n);++n; static int x; Rep(i,2,n)read(s[i]),read(p[i]),read(x),++x,ed[x].push_back(i); } static double dp[MAXN][MAXN],w[MAXN]; const double eps=1e-5; static int dfn[MAXN],nx[MAXN],e=0; void dfs(int u){dfn[u]=++e;for(int v:ed[u])dfs(v);nx[dfn[u]]=e+1;} inline bool Judge(double num) { Rep(i,2,n)w[dfn[i]]=1.*p[i]-num*s[i]; w[0]=0; Rep(i,2,n+1)Rep(j,0,m+1)dp[i][j]=-1e12; Rep(i,1,n) { Rep(j,0,m+1)if(dp[i][j]>-1e9) { Chkmax(dp[i+1][j+1],(dp[i][j]+w[i])); Chkmax(dp[nx[i]][j],dp[i][j]); } } return dp[n+1][m+1]>1e-5; } inline void solve() { Rep(i,1,m+1)dp[1][i]=-1e12;dp[1][0]=0; dfs(1); static double l=0.0,r=1e5,mid; while(r-l>eps) { mid=(l+r)/2; if(Judge(mid))l=mid; else r=mid; } printf("%.3lf\n",l); } int main() { file(); init(); solve(); return 0; } ```