JSOI 信息学代表队一共有 $N$ 名候选人，这些候选人从 $1$ 到 $N$ 编号。方便起见，JYY 的编号是 $0$ 号。每个候选人都由一位编号比他小的候选人$R_i$推荐。如果 $R_i = 0$ ，则说明这个候选人是 JYY 自己看上的。
为了保证团队的和谐，JYY 需要保证，如果招募了候选人 $i$，那么候选人 $R_i$ 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 $P_i$ ，也有一个招募费用 $S_i$。JYY 希望招募 $K$ 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 $K$ 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。
链接
Luogu P4322
代码
这题看着很高端…事实上就是一个0/1分数规划+树形dp…
0/1分数规划的过程，就是二分选择一个答案 $ans$ ，然后去验证能不能取到若干个 $P_i - ans \times S_i$ 大于0。
能不能取到这个大于 $0$ 的东西，用 $O(n^2)$ 的树形dp验证一下就好了。
我这个代码好像有点锅，不开O2就RE…懒得找了…就这样吧…
这里的初始化也要注意一下，还有就是循环的边界，因为这里父节点必须取，第一层循环就不能到 $0$ …
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 3000;
const double eps = 1e-4;
int n,m;
double s[MAXN],p[MAXN];
int siz[MAXN];
double dp[MAXN][MAXN];
vector<int> edge[MAXN];
double k;
double tmp[MAXN];
void dfs(int x){
for(int j = 0;j < MAXN;j++)
dp[x][j] = -1e9;
siz[x] = 1;dp[x][0] = 0;dp[x][1] = p[x] - k*s[x];
for(int i = 0;i<edge[x].size();i++){
int v = edge[x][i];
dfs(v);
for(int j = 0;j<=siz[x] + siz[v];j++)
tmp[j] = -1e9;
for(int j = 0;j<=siz[x];j++)
tmp[j] = dp[x][j];
for(int j = siz[x];j >= 1;--j)
for(int w = siz[v];w >= 0;--w)
if(j+w <= m)
tmp[j+w] = max(tmp[j+w],dp[x][j] + dp[v][w]);
memcpy(dp[x],tmp,sizeof(double)*(siz[x] + siz[v]+1));
siz[x] += siz[v];
}
}
bool check(double num){
k = num;
dfs(0);
return dp[0][m] > -eps;
}
int main(){
scanf("%d %d",&m,&n);m++;
int f;
for(int i = 1;i<=n;i++){
scanf("%lf %lf %d",&s[i],&p[i],&f);
edge[f].push_back(i);
}
double l = 0,r = 10000;
while(r - l > eps){
double mid = (l+r)/2;
if(check(mid))
l = mid;
else
r = mid;
}
printf("%.3lf\n",l);
return 0;
}
|
