Loj10154 选课

试题描述：

大学实行学分制。每门课程都有一定的学分，学生只要选修了这门课并通过考核就能获得相应学分。学生最后的学分是他选修各门课的学分总和。
每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程基础上才能选修。例如《数据结构》必须在选修了《高级语言程序设计》后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为 1,2,3…
上例中课号1是课号2的先修课，即如果要先修课号2，则课号1必定已被选过。同样，如果要选修课号3，那么课号1和课号2都一定被选修过。
学生不可能学完大学开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程间不存在时间上的冲突。

首先能一眼看出来，这些课程是一个树形结构，对于每一个节点i，都需要判断它的所有儿子是否取，又往下取多少。

这样我们把问题转化成了一个分组背包：对于每一个节点，每一颗子树就是一组，每一组又m（也就是选课数）个物品，第i物品的体积是i，价值是f[j][i](j为当前儿子）

然后转移方程就可以变为f[i][j][k]表示在以i为根节点的子树中，第j组，取k个物品的最优值。

易得到：f[i][j][k]=max(f[i][j][k],f[i][j-1][k-q](q为枚举物品）+f[i][y][q])(y为子节点）

然后，我们发现可以把j的那一位压去，但是注意循环要倒着写。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#define MAXN 1010

#define in(a) a=read()

#define REP(i,k,n)  for(int i=k;i<=n;i++)

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

int total,head[MAXN],to[MAXN<<],nxt[MAXN<<],f[MAXN][MAXN],s[MAXN];

inline void adl(int a,int b){

    total++;

    to[total]=b;

    nxt[total]=head[a];

    head[a]=total;

    return ;

}

inline void dfs(int i){

    for(int e=head[i];e;e=nxt[e]){

        dfs(to[e]);

        for(int j=m;j>=;j--)

            REP(k,,j)

                f[i][j]=max(f[i][j],f[i][j-k]+f[to[e]][k]);

    }

    if(i)  for(int j=m;j>;j--)  f[i][j]=f[i][j-]+s[i];

    return ;

}

int main(){

    in(n),in(m);

    int a,b;

    REP(i,,n)  in(a),in(s[i]),adl(a,i);

    dfs();

    cout<<f[][m];

    return ;

}

巴特西

Loj10154 选课

最新文章

热门文章