[Luogu2014]选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有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：

7 4

2 2

0 1

0 4

2 1

7 1

7 6

2 2

输出样例#1：

13

树上背包的较简单题吧

$F[i][j]$表示到第$i$个节点，选了$j$门课程所得的最大得分。

\[F[i][j]=max(F[son][l]+F[i][j-l])$$$$0<=l<=j
\]

然后就可以愉快地$dp$啦

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*w;

}

int n,m,cnt;

int v[310],head[310];

int dp[310][310];

struct node{

    int to,next;

}edge[410];

void add(int x,int y)

{

    cnt++;

    edge[cnt].to=y;

    edge[cnt].next=head[x];

    head[x]=cnt;

}

void dfs(int k)

{

    int u;

    for(int i=head[k];i;i=edge[i].next)

    {

        u=edge[i].to;

        dfs(u);

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

        {

            for(int l=j;l>=0;l--)

            {

                dp[k][j]=max(dp[k][j],dp[k][l]+dp[u][j-l]);

            }

        }

    }

    if(k!=0)

    {

        for(int i=m;i>=1;i--)

        dp[k][i]=dp[k][i-1]+v[k];

    }

}

int main()

{

    int x,y;

    n=read();m=read();

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

    {

        x=read();y=read();

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

    }

    dfs(0);

    int ans=0;

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

    ans=max(ans,dp[i][m]);

    cout<<ans;

}

巴特西

[Luogu2014]选课（树形dp）

[Luogu2014]选课

题目描述

输入输出格式

输入输出样例

最新文章

热门文章