vijos P1180 选课 树形dp

题目地址:p1180选课
多叉的情况不好做,所以可以转换成二叉树.
那么设dp[i][j]为以i为根节点的子树上选择j门课.
dp[i][j] = max(dp[right][j], dp[left][k - 1] +dp[right][j - k] + credit[i] | 1<= k <= j)

转移方程时一定要注意右儿子都是兄弟不是儿子

因为转换成了二叉树,所以任何节点i的右节点是其多叉树上的兄弟节点,左节点才是多叉树的子树.
所以dp[right][j]为把j课全部安排在兄弟节点子树上,dp[left][k - 1]为安排一门课在i上,安排k - 1门在子数上,安排j - k门在兄弟节点子树上.
总的复杂度为O(n^3)
转自 蚂蚁大战大象

#include <cstdio>

#include <vector>

#include <memory.h>

using namespace std;
const int MAX =305;
vector<int> t[MAX];
int credit[MAX], L[MAX], R[MAX];
int dp[MAX][MAX];
int dfs(int i, int j){
if(i == -1)return 0;
else if(j <= 0)return 0;
else if(dp[i][j] != -1)return dp[i][j];
dp[i][j] = dfs(R[i], j);
for(int m = 1; m <= j; ++m){
dp[i][j] = max(dp[i][j], dfs(L[i], m - 1) + dfs(R[i], j - m) + credit[i]);
}
return dp[i][j];
}
int main(int argc, char const *argv[]){
int N, M;
memset(L, -1, sizeof(L));
memset(R, -1, sizeof(R));
memset(dp, -1, sizeof(dp));
scanf("%d%d", &N,
&M);
for(int i = 1; i <= N; ++i){
int pre;
scanf("%d %d", &pre, &credit[i]);
t[pre].push_back(i);
}
for(int i = 0 ; i <= N; ++i){
if(t[i].size() > 0){
L[i] = t[i][0];
int rc = t[i][0];
for(int j = 1; j < t[i].size();++j){
R[rc] = t[i][j];
rc = t[i][j];
}
}
}
printf("%dn", dfs(0, M + 1));
return 0;
} 

注意：输出要用dp[0][M+1]，因为多了一个根节点0

最后

以上就是妩媚香氛为你收集整理的vijos P1180 选课 树形dp的全部内容，希望文章能够帮你解决vijos P1180 选课 树形dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。