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思路.

状态定义：

f[ i ] [ j ] 表示当前 i 这个节点,已经选了 j 个的最大价值

状态转移:

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

for ( k=1 ; k<=m; k++ )

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

类似于01背包的转移方程，只是把它放到了树上而已.

然后我进行了一个预处理,预先将每个节点的子树节点个数记录起来,然后在转移的时候就只要转移 min (num[now],m );

优化到了 0ms.

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

struct sj{

    int to;

    int next;

}a[maxn];

int c[maxn],v[maxn],ans;

int size,head[maxn],n,m;

int f[maxn][maxn],num[maxn];

void add(int x,int y)

{

    a[++size].to=y;

    a[size].next=head[x];

    head[x]=size;

}

void pre(int x)

{

    num[x]=;

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(!num[tt])

        {

            pre(tt);

            num[x]+=num[tt];

        }

    }

    f[x][]=c[x];

    return;

}

void dfs(int x)

{

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        dfs(tt);

        int jj=min(m,num[x]);

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

        for(int k=;k<j;k++)

        f[x][j]=max(f[x][j],f[tt][k]+f[x][j-k]);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        c[i]=y; add(x,i);

    }

    m++;

    //此处因为 0 对于答案不算体积.

    pre();

    dfs();

    cout<<f[][m]<<endl;

    return ;

}

巴特西

P2014 选课 (树形动规)

题目描述

输入输出格式

输入输出样例

Solution

代码

最新文章

热门文章