題目描述

在大學里每個學生，為了達到一定的學分，必須從很多課程里選擇一些課程來學習，在課程里有些課程必須在某些課程之前學習，如高等數(shù)學總是在其它課程之前學習。現(xiàn)在有N門功課，每門課有個學分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學完了課程a，才能學習課程b）。一個學生要從這些課程里選擇M門課程學習，問他能獲得的最大學分是多少？

輸入格式

第一行有兩個整數(shù)N,M用空格隔開。(1<=N<=300,1<=M<=300)

接下來的N行,第I+1行包含兩個整數(shù)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

#include<iostream> #include<algorithm> #include<queue> #include<cstdio> #include<cstring> using namespace std; vector<int>edge[1000]; int val[1000],dp[1000][1000],n,m; void dfs(int u,int t) {if (t<=0) return ;for (int i=0;i<edge[u].size(); i++){int v = edge[u][i];for (int k=0; k<t; ++k) dp[v][k] = dp[u][k]+val[v];dfs(v,t-1);for (int k=1; k<=t; ++k) dp[u][k] = max(dp[u][k],dp[v][k-1]);} } int main() {scanf("%d%d",&n,&m);for(int i=1,a;i<=n;i++){scanf("%d%d",&a,&val[i]);edge[a].push_back(i);}dfs(0,m);printf("%d",dp[0][m]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的洛谷2014 选课（树形DP)树形背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。