考察:树形背包dp
思路:
首先我们需要拿一个变量作为背包的体积,不能以钱数做体积,因为范围没有给定.所以只能以人数做体积.f[i][j]表示以i为根节点的子树中,选j个人的最大花费.如果>=0表示方案可行.因为人数是可以枚举的,所以不会漏解.
这里要注意的是背包体积不能直接设为m,否则会TLE,因f[i][j]是被优化为二维的dp,实际三维dp是f[i][j][k] 以i为根节点的子树中,前j个子节点中选k个人,明显j那一维是可以优化掉的.k的取值范围是当前子节点个数.所以dfs需要返回当前子节点个数.
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5 const int N = 3010;
6 int m,n,idx,h[N],w[N],money[N],cnt[N];
7 int f[N][N];
8 struct Road{
9 int fr,to,ne;
10 }road[N];
11 void add(int a,int b)
12 {
13 road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
14 }
15 void init()
16 {
17 scanf("%d%d",&n,&m);
18 memset(f,-0x3f,sizeof f);
19 memset(h,-1,sizeof h);
20 for(int i=1;i<=n-m;i++)
21 {
22 int k; scanf("%d",&k);
23 while(k--)
24 {
25 int s,p; scanf("%d%d",&s,&p);
26 add(i,s); w[s] = p;
27 }
28 }
29 for(int i=n-m+1;i<=n;i++) scanf("%d",&money[i]),cnt[i] = 1;
30 }
31 int dfs(int u)
32 {
33 f[u][0] = 0;
34 int sum = 1;
35 for(int i=h[u];i!=-1;i=road[i].ne)
36 {
37 int v = road[i].to;
38 sum+=dfs(v);//不倒序会选到重复的点.
39 for(int j=sum;j>=0;j--)//多少人
40 for(int k=0;k<=j;k++)//子节点多少人
41 f[u][j] = max(f[v][k]+f[u][j-k],f[u][j]);
42 }
43 for(int i=sum;i>=1;i--)
44 f[u][i] = f[u][i-cnt[u]]-w[u]+money[u];
45 return sum;
46 }
47 int main()
48 {
49 init();
50 int s = dfs(1);
51 for(int i=s;i>=0;i--)
52 if(f[1][i]>=0) {printf("%d\n",i);return 0;}
53 return 0;
54 }