P2014 选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

输入输出格式

输入格式：

第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)

接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。

输出格式：

只有一行，选M门课程的最大得分。

输入输出样例

输入样例#1：

输出样例#1：

Solution:

　　本题是一道树上背包类$DP$问题。

　　由于本题的图是一个森林，所以我们加一个根节点$0$连向各个森林，形成一棵新树。

　　定义状态$f[i][j]$表示在以$i$为根节点的子树中选了$j$个节点的最大价值。

　　则不难想到状态转移方程：$f[i][j]=max(f[i][j],f[i][j-k]+f[v][k])$其中$v$是$i$的子节点，表示在$i$的子节点中选了$j-k$个物品和在$v$子树上选$k$个物品的最大价值。

　　回溯时注意逆序赋值：$f[i][j]=f[i][j-1]+w[i]$表示在$i$子树上选$j$个物品必须先选$i$节点，逆序是为了防止重复选$i$物品。

　　最后输出目标状态$f[0][m]$就$OK$了。

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)>(b)?(a):(b))
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=305;
int n,m,f[N][N],h[N],cnt,to[N],net[N],rd[N],w[N];
il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,rd[v]++;}
il void dfs(int u){
    f[u][0]=0;
    for(int i=h[u];i;i=net[i]){
        int v=to[i];
        dfs(v);
        Bor(k,0,m) Bor(j,0,k)f[u][k]=Max(f[u][k],f[u][k-j]+f[v][j]);
    }
    if(u) Bor(j,1,m) f[u][j]=f[u][j-1]+w[u];
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    memset(f,-1,sizeof(f));
    int x;
    For(i,1,n){cin>>x>>w[i];if(x)add(x,i);}
    For(i,1,n)if(!rd[i])add(0,i);
    dfs(0);
    cout<<f[0][m];
    return 0;
}