洛谷P2014 选课(先序遍历优化树形背包)

zeroy0410

2018-08-23 10:27:49

Solution

#### 题目 在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少? #### 思路 各种课程之间的关系显然是树形结构,显然可以用背包求解。 我们用$dp[x][j]$表示在当前子树中选择了j门课所能获得的最大学分,之后每个点就都可以由它的子节点转移了。 ```c++ #include<bits/stdc++.h> #define M 305 using namespace std; int n,m; vector<int>G[M]; int A[M],sz[M]; int dp[M][M]; void dfs(int x,int f){ int k=G[x].size(); dp[x][1]=A[x];sz[x]=1; for(int i=0;i<k;i++){ int u=G[x][i]; if(u==f)continue; dfs(u,x); sz[x]+=sz[u]; for(int j=min(m+1,sz[x]);j>=2;j--) for(int k=1;k<j;k++) dp[x][j]=max(dp[x][j],dp[x][k]+dp[u][j-k]); } } int main(){ cin>>n>>m; for(int i=1,a;i<=n;i++){ scanf("%d%d",&a,&A[i]); G[a].push_back(i); } dfs(0,-1); cout<<dp[0][m+1]<<endl; return 0; } ``` #### **然而,这不是重点** 我们会发现以上的思路的复杂度是$O(n*m^2)$,那我们能不能寻求更优的复杂度呢? 对于一棵子树而言,对于它我们只有两种状态,要么将其选中,同时选它子树中的点,要么直接跳过这一棵子树,所以我们不妨这样定义dp数组: $dp[x][j]$表示当前节点和它的兄弟节点中选j门课的最小值。 对于每个点,我们要记录子树的大小,和dfs序。 不难发现以下状态转移方程: $dp[i][j]=max(dp[i+sz[ln[i]]][j],dp[i+1][j-1]+A[ln[i]]);$ 即对于当前点而言,直接跳过这棵子树的情况,和搜集它子树内的信息。 因为树上的问题有着天然的顺序,所以,我们按dfs序倒着循环一遍就行了。 ```c++ #include<bits/stdc++.h> #define M 505 using namespace std; int n,m,dp[M][M],A[M],sz[M]; vector<int>G[M]; int ln[M],tt; void dfs(int x){ ln[++tt]=x;sz[x]=1; for(int i=0;i<G[x].size();i++){ int u=G[x][i]; dfs(u); sz[x]+=sz[u]; } } int main(){ cin>>n>>m; for(int i=1,a,b;i<=n;i++) scanf("%d%d",&a,&A[i]),G[a].push_back(i); dfs(0); for(int i=n+1;i>=1;i--) for(int j=1;j<=m+1;j++) dp[i][j]=max(dp[i+sz[ln[i]]][j],dp[i+1][j-1]+A[ln[i]]); cout<<dp[1][m+1]<<endl; return 0; } ``` 对先序遍历优化树形背包不是很熟悉的同学可以去看看这个:[网页链接](http://note.youdao.com/noteshare?id=07619acf27a64381650dbb9dc2000f68&sub=4FCC06D686104EA19BFFBF85E614343D)