洛谷P2014 选课(树形dp)

选课

题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有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[i][j],f[son][j-k]+f[i][k])。

代码

#include <cstdio>
#define N 500
using namespace std;
struct arr
{
int to,nxt;
}a[N];
int b[N],f[N][N],ls[N],l,n,m;
bool v[N];
void add(int x, int y)
{
a[++l].to = y;
a[l].nxt = ls[x];
ls[x] = l;
}
int max(int x, int y){return x>y?x:y;}
void dfs(int x)
{
v[x] = true;
f[x][1] = b[x];
for (int i = ls[x]; i; i = a[i].nxt)
if (!v[a[i].to])
{
dfs(a[i].to);
for (int j = m + 1; j > 0; j--)
for (int k = 0; k < j; k++)
f[x][j] = max(f[x][j], f[x][j - k] + f[a[i].to][k]);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d%d", &x, &b[i]);
add(x, i);
}
dfs(0);
printf("%d", f[0][m+1]);
}

最后

以上就是典雅小刺猬为你收集整理的洛谷P2014 选课(树形dp)的全部内容，希望文章能够帮你解决洛谷P2014 选课(树形dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。