【题解】洛谷P4322 [JSOI2016]最佳团体01分数规划+树上背包

给定N(2500)，K(2500)，N+1个点的一棵树（以0为根），每个节点有属性$P_i,S_i$。

从树中选择$K+1$个点，使得$\Sigma P_i/\Sigma S_i$最大，必须满足选择一个点时它的父节点也被选择。

---

01分规：

设最优解为$x_0$，那么$\Sigma P_i-x_0\Sigma S_i\le 0$

设$F(x)=ma{x}_d\{\Sigma P_i-x\Sigma S_i\}$，$F(x)$单调递减，$F(x)$的零点就是答案$x_0$。

树上背包

设$c_i=P_i-x{S}_i$，现在的目标是从树中选$k+1$个点使得$c_i$之和最大，可以做树上背包。

$dp[i][j]$表示在以第$i$个点为根的子树中选择$j$个点的最大价值

$dp[i][j]=max\{dp[i][j-k]+dp[v][k]\}$

$dp[i][0]=-inf，dp[i][1]=c_i$，表示不能不选父节点只选子节点。

---

不开O2略卡常数，改成链式前向星+部分初始化后通过。

/* LittleFall : Hello! */ #include <bits/stdc++.h> using namespace std; using ll = long long; inline int read(); const int M = 2516, MOD = 1000000007; inline int dcmp(double a, double b) { if(fabs(a-b)<1e-6) return 0; return a>b?1:-1; } int pnt[M], lst[M], fst[M], ecn; //链式前向星 int siz[M]; //节点管辖范围 void dfs0(int u) { siz[u] = 1; for(int e=fst[u]; e; e=lst[e]) { dfs0(pnt[e]); siz[u] += siz[pnt[e]]; } } int k, n, s[M], p[M]; double dp[M][M]; int dfs(int u) { int cnt = 1; for(int e=fst[u]; e; e=lst[e]) { int v=pnt[e], cntv = dfs(v); for(int j=min(k+1, cntv+cnt); j>=1; --j) for(int k=max(0, j-cnt), rk=min(cntv,j); k<=rk; ++k) dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[v][k]); cnt += cntv; } return cnt; } int main(void) { #ifdef _LITTLEFALL_ freopen("in.txt","r",stdin); #endif k = read(), n = read(); for(int i=1; i<=n; ++i) { s[i] = read(), p[i] = read(); int fa = read(); pnt[++ecn] = i, lst[ecn] = fst[fa], fst[fa] = ecn; } s[0] = p[0] = 0; dfs0(0); double l=0, r=10000; while(dcmp(l,r)<0) { double m = (l+r)/2; for(int i=0; i<=n; ++i) { for(int j=0; j<=siz[i]; ++j) dp[i][j] = -1e18; dp[i][1] = p[i] - s[i]*m; } dfs(0); if(dcmp(dp[0][k+1],0)>=0) l = m; else r = m; } printf("%.3f\n",l ); return 0; } inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }