选课

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1098 字

M门课，选恰好N门，选课需先选修先修课，求最

一本通
例

正文

/*
原题：选课（一本通 5.2 例2）
题意：M 门课，选恰好 N 门，选课需先选修先修课（每门先修最多一门），求最大学分。
思路：建虚根 0，先修为 0 的课作 0 的儿子，形成森林。树形背包 dp[u][k] 表示 u 子树选 k 门（含 u）的最大学分，儿子被选中时父必被选中。答案 dp[0][N+1]（含虚根）。
复杂度：O(M*N^2) 时间，O(M*N) 空间。
易错点：虚根不占课程数，选 N 门实为 dp[0][N+1]；合并儿子时父必须被选中。
*/
#include <bits/stdc++.h>
using namespace std;
const int M=105;
const int INF=1e9;
int m,n;
vector<int> g[M];
int credit[M];
int dp[M][M];
int sz[M];
void dfs(int u){
    sz[u]=1;
    for(int j=0;j<=n+1;j++)dp[u][j]=-INF;
    dp[u][0]=0;
    dp[u][1]=credit[u];
    for(int v:g[u]){
        dfs(v);
        for(int j=sz[u]+sz[v];j>=0;j--){
            int best=dp[u][j];
            for(int k=0;k<=sz[v]&&k<=j;k++){
                if(k>=1&&j-k<1)continue;
                best=max(best,dp[u][j-k]+dp[v][k]);
            }
            dp[u][j]=best;
        }
        sz[u]+=sz[v];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        int pre,c;
        cin>>pre>>c;
        credit[i]=c;
        g[pre].push_back(i);
    }
    credit[0]=0;
    dfs(0);
    cout<<dp[0][n+1]<<"\n";
    return 0;
}

选课

正文

一本通·提高篇的其它内容