首先,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:
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例#1:
13
树形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 ;
}
相似题目链接