P2014 選課
時間限制 1.00s
內存限制 125.00MB

題目描述
在大學里每個學生，為了達到一定的學分，必須從很多課程里選擇一些課程來學習，在課程里有些課程必須在某些課程之前學習，如高等數學總是在其它課程之前學習。現在有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[u][j]$表示以$u$為父節點選取$j$門課后所能獲得的最大學分。
則$dp[u][j]=max(dp[u][j],dp[u][j?k]+dp[v][k])$
因此需循環更新一下$dp[u][j]$的值

for(int i=0;i<m[s].size();i++) {dfs(m[s][i]);for(int j=M;j>=0;j--) {for(int k=j;k>=0;k--) {dp[s][j]=max(dp[s][j],dp[s][j-k]+dp[m[s][i]][k]);}}}

但這時并未將父節點本身的價值算進去，因此還需更新一下加入父節點的值

if(s!=0) {for(int i=M;i>=1;i--) {dp[s][i]=dp[s][i-1]+val[s];}}

完整代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int dp[310][310];
vector<int> m[310];
int val[310];
int N,M;
void dfs(int s) {for(int i=0;i<m[s].size();i++) {dfs(m[s][i]);for(int j=M;j>=0;j--) {for(int k=j;k>=0;k--) {dp[s][j]=max(dp[s][j],dp[s][j-k]+dp[m[s][i]][k]);}}}if(s!=0) {for(int i=M;i>=1;i--) {dp[s][i]=dp[s][i-1]+val[s];}}
}
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);scanf("%d %d",&N,&M);int a,b;rep(i,1,N) {scanf("%d %d",&a,&b);m[a].push_back(i);val[i]=b;}dfs(0);printf("%d\n",dp[0][M]);return 0;
}