选课[树形dp]

链接1:选课[树形dp]
链接2:选课[树形dp]

题解

  • 乍一看是有依赖的背包问题,然而并不是。因为有依赖的背包问题没有间接依赖关系,然而这题有
  • 正解是树形dp。
  • 建图之后是一个森林? 人为加一个源点就OK
  • 因为第二个链接中要求输出决策 我建图为二叉树,多跑一遍dfs记录决策

    多叉树

    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
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #include<algorithm>
    #include<set>
    #include<vector>
    #include<map>
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e3;
    vector<int>edge[N];
    int dp[N][N],pre[N],n,m,w[N],root;
    void dfs(int u){
    rep(i,1,m)dp[u][i]=w[u];
    int len=edge[u].size()-1;
    rep(i,0,len){
    int v=edge[u][i];
    dfs(v);
    repd(j,m,1)rep(k,1,(u==root?j:j-1))dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
    }
    }
    int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
    scanf("%d%d",&pre[i],&w[i]);
    if(pre[i])edge[pre[i]].push_back(i);
    }
    root=0;
    rep(i,1,n)if(!pre[i])edge[root].push_back(i);
    dfs(root);
    cout<<dp[root][m]<<endl;
    return 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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e3;
int dp[N][N],lson[N],rson[N],w[N],n,m,ans[N];
void maketree(){
scanf("%d%d",&n,&m);
rep(i,1,n){
int a,b;
scanf("%d%d",&a,&b);
w[i]=b;
rson[i]=lson[a];
lson[a]=i;
}
}
void dfs(int x,int y){
if(dp[x][y]||x==0||y==0)return ;
dfs(rson[x],y);
rep(i,0,y-1){
dfs(rson[x],i);
dfs(lson[x],y-i-1);
dp[x][y]=max(dp[x][y],max(dp[rson[x]][y],dp[rson[x]][i]+dp[lson[x]][y-i-1]+w[x]));
}
}
void path(int x,int y){
if(x==0||y==0){dp[x][y]=0;return;}
dfs(rson[x],y);
rep(i,0,y-1)if(dp[x][y]==dp[rson[x]][i]+dp[lson[x]][y-i-1]+w[x]){
path(rson[x],i);
path(lson[x],y-i-1);
ans[x]=1;
}
}
int main(){
maketree();
dfs(lson[0],m);
path(lson[0],m);
cout<<dp[lson[0]][m]<<endl;
rep(i,1,n)if(ans[i])cout<<i<<endl;
return 0;
}