洛谷P2014题解_牛客博客

首先，2014这个题号给人一种很特殊的感觉啊！~~~

昂，由于刚刚学了树形DP，所以便做了这道题。

（我的意思是若有写的不好的地方尽量包涵，尽量QwQ~~）

题目描述

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

树形DP

f[i][j] 表示第i各节点取第j个儿子时的最max（min）价值

状态转移方程

F[i][j]=max/min(f[i][j],f[i][j-k]+f[儿子节点编号][k]=....)

代码如下：

（由于我也是学的，所以说有和别的相似的不要吐槽了楼~~）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 2018 ;
int n , m , f[maxn][maxn] ;
int head[maxn] , next[maxn] , w[maxn] ;//head[],next[]数组模拟邻接表，w[]用来存边权
int dfs(int x){
	int sum = 0 ;
	for(int i = head[x] ; i != -1 ; i = next[i])//这里就类似于一个背包了！！
	{
		int t = dfs(i) ;
		sum += t + 1 ;
		for(int j = sum ; j >= 0 ; j --)
		for(int k = 0 ; k <= t ; k ++)
		if(j - k - 1 >= 0) f[x][j] = max(f[x][j] , f[x][j-k-1] + f[i][k]) ;//状态转移方程上面有讲
	}
	return sum ; 
}
int main(){
	scanf("%d%d",&n,&m) ;//输入点数，选择的个数
	memset(head,-1,sizeof(head)) ;
//用链性表来储存
	for(int i = 1 ; i <= n ; i ++)
	{
		int x ;
		scanf("%d%d",&x,&w[i]) ;//存一棵树，不多解释
		next[i] = head[x] ;
		head[x] = i ;
	}
	for(int i = 1 ; i <= n ; i ++) f[i][0] = w[i] ;
	dfs(0);
	printf("%d\n",f[0][m]) ;
	return 0 ;
}

相似题目链接