P2014 [CTSC1997] 选课

原题链接

题解

解法一：三维dp，dp[ root ][ j ][ k ] 含义，以root为根结点的树中只在前 j 棵子树 中选 k 门课程的最大学分。

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int val[305],num[305];
int dp[305][305][305];
vector<vector<int > > G(302);

int f(int root,int j,int k){
    if (k==0) return 0;
    if (k==1 || j==0) return val[root];
    if (dp[root][j][k]) return dp[root][j][k];
    int ans=f(root,j-1,k);
    for (int s=1;s<k;s++){
        int x=G[root][j-1];
        ans=max(ans,f(root,j-1,k-s)+f(x,num[x],s));
    }
    dp[root][j][k]=ans;
    //cout<<root <<" "<<j<<" "<<k<<" "<<ans<<endl; 
    return ans;
}

int main(){
    cin>>n>>m;
    for (int i=1,k;i<=n;i++){
        cin>>k>>val[i];
        G[k].push_back(i);
        num[k]++;
    }
    
    cout<<f(0,num[0],m+1)<<endl;
    return 0;
}

解法二：dfs序优化

code

#include<bits/stdc++.h>
using namespace std;
int head[305],Next[305],to[305],val[305],cnt=1;
int size[305],dfn[305],value[305];
int dp[305][305];

void build(int from,int to_){
    Next[cnt]=head[from];
    to[cnt]=to_;
    head[from]=cnt++;
}

void dfs(int root){
    int i=cnt++;
    dfn[root]=i;
    value[i]=val[root];
    size[i]=1;
    for (int j=head[root];j>0;j=Next[j]){
        dfs(to[j]);
        size[i]+=size[dfn[to[j]]];
    }
    //cout<<root<<" "<<dfn[root]<<" "<<value[i]<<" "<<size[i]<<endl;
}

int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1,k,s;i<=n;i++){
        cin>>k>>val[i];
        build(k,i);
    }
    cnt=1;
    
    dfs(0);
    
    for (int i=n+1;i>=1;i--){
        for (int j=1;j<=m+1;j++){
            dp[i][j]=max(dp[i+size[i]][j],dp[i+1][j-1]+value[i]);
        }
        
    }
    cout<<dp[1][m+1]<<endl;
    return 0;
}