【题目链接】

【调试出错】

写了第一遍怎么调都不过，气得想摔键盘。

冷静去上了两节文化课回来又码了一遍，然后就一遍过了。

【题解大意】

这个题目给的是森林，我们构建虚拟节点0使之变成一棵树。

f[x,t]表示以x为根的子树中选择t门课程能获得的最高学分。设x的子节点集合为son[x]。

【code】

#include
      
       using namespace std;const int N = 306;vector
       
         son[N];int n, m, f[N][N], s[N];void dp(int x) {    f[x][0] = 0;    for (unsigned int i = 0; i < son[x].size(); i++) {        int y = son[x][i];        dp(y);        for (int t = m; t >= 0; t--)            for (int j = t; j >= 0; j--)                if (t - j >= 0)                    f[x][t] = max(f[x][t], f[x][t-j] + f[y][j]);    }    if (x) for(int t = m; t; t--) f[x][t] = f[x][t-1] + s[x];}int main() {    cin >> n >> m;    for (int i = 1; i <= n; i++) {        int x;        cin >> x >> s[i];        son[x].push_back(i);    }    memset(f, 0xcf, sizeof(f));    dp(0);    cout << f[0][m] << endl;    return 0;}
       
      

 【题目链接】传送门

【题解大意】

输出方案！

一般dp怎么输出方案呢。

用与dp状态大小相同的数组记录出当前的最优值是由什么转移而来的，通过一次递归沿着记录的状态来源回到最初状态。

【code】