10154. 「一本通 5.2 例 2」选课

题意

有很多课程,但部分课程有先修课。学生不可能学完大学开设的所有课程,因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。请找出一种选课方案使得你能得到的学分最多,并满足先修课优先的原则。假定课程间不存在时间上的冲突。

思路

瞎搞树形DP。

发现这是背包。

还是分组背包。(^▽^)

于是就愉快地解决了。

设$f[x][t]$表示以x为根节点的子树中选t门课能够获得的最高学分。(所以说是背包问题嘛)
$$Answer:f[0][m]$$

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
#define eps 1e-4
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void write(int zx){
if(zx<0){zx=-zx;putchar('-');}
if(zx<10) putchar(zx+'0');
else{
write(zx/10);
putchar(zx%10+'0');
}
}
int n,m,fir[310],nxt[310];
int s[310],w[310],f[310][310];
int DP(int x){
if(fir[x]==-1) return 0;
int sum=0;
for(int i=fir[x];i!=-1;i=nxt[i]){
int tmp=DP(i);
sum+=tmp+1;
for(int j=sum;j>=0;j--)
for(int k=0;k<=tmp;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(){
n=read();m=read();
memset(fir,-1,sizeof(fir));
for(int i=1;i<=n;i++){
s[i]=read();w[i]=read();
nxt[i]=fir[s[i]];
fir[s[i]]=i;
}
for(int i=1;i<=n;i++) f[i][0]=w[i];
f[0][0]=0;
DP(0);
write(f[0][m]);
putchar('\n');
return 0;
}

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×