并没有什么用的更新时间

【2019/03/12】 题目及代码更新
【2019/03/19】题解更新

选课

• 题目描述
  在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有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的典型例题
  ②得知此题输入为多叉树，需把多叉树转为二叉树。读入儿子节点和父亲节点，如果这个父亲节点没有子节点，就把儿子节点变成它的左节点，否则变为它最新子节点的右节点（左儿子右兄弟）
  ③DP式为f[x][y]=max(f[x][y],f[l[x]][i-1]+v[x]+f[r[x]][y-i])，f[x][y]表示在x节点及它的子节点放y个人的最大价值，l[x]表示x节点的左节点，r[x]表示x节点的右节点,v[x]为x节点的权值,i是循环模拟在x节点及它的子节点放几个人
  ④先将f数组初始化为-1方便判断出界
  ⑤DP前把f[x][y]的值初始化为它的右节点（不要问我为什么，应该是因为右兄弟比较多吧 ）
• 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=605,maxm=605;
int n,m,f[maxn][maxm],v[maxn],l[maxn],r[maxn],dis[maxn];
void dp(int x,int y){
if (f[x][y]==-1){
dp(r[x],y);
f[x][y]=f[r[x]][y];
for (int i=1;i<=y;++i){
dp(r[x],y-i);
dp(l[x],i-1);
f[x][y]=max(f[x][y],f[l[x]][i-1]+v[x]+f[r[x]][y-i]);
}
}
}
int main(){
cin>>n>>m;
for (int i=1;i<=n;++i){
int x;
cin>>x>>v[i];
if (dis[x]==0) l[x]=i;
else r[dis[x]]=i;
dis[x]=i;
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) f[i][j]=-1;
dp(l[0],m);
cout<<f[l[0]][m]<<endl;
}

• 相关连接

洛谷P2014

最后

以上就是内向百合最近收集整理的关于【树形DP】选课并没有什么用的更新时间选课的全部内容，更多相关【树形DP】选课并没有什么用内容请搜索靠谱客的其他文章。