首页 > 其他 > 详细

CTSC1998 选课(背包类树形Dp)

时间:2018-11-15 00:49:39      阅读:145      评论:0      收藏:0      [点我收藏+]

题意:

给出 n 节课的先修课号以及学分(先修课号指的是在学习某节课时先需要学习的课程),求学 m 节课的最大学分。

细节:

1、对于课程 a 其先修课号为 b ,对于课程 b 其先修课号为 c ,则需要学 a 的方式必须为先学 c 在学 b
2、可能存在多门课程没有先修课号。

分析:

题目给出的先修课号是唯一的,所以我们可以将这种依赖关系构建成一棵树,所以对于每个节点的学分之和就是为从根节点到其的简单路径,所以对于每个节点相当于一个背包。

所以状态就是:dp[u][j] 表示以 u 为根的子树选了 j 门课所获得最大学分

转移就是:dp[u][j] = max( dp[u][j] , dp[u][j-k] + dp[v][k] ) 
其中 dp[u][1] = dist[u] , 1 ≤ j ≤ size[u] , 0≤k≤min( size[v] , j-1)

代码:

#include <bits/stdc++.h>
#define MAXN 305
using namespace std;

int f[MAXN][MAXN], dist[MAXN], size[MAXN], n, m;
vector <int> G[MAXN];

void build(int u){
    size[u]=1;
    for (int i=0; i<G[u].size(); i++){
        int v=G[u][i];
        build(v);
        size[u]+=size[v];
    }

}

void solve(int u){
    f[u][1]=dist[u];
    for (int i=0; i<G[u].size(); i++){
        int v=G[u][i];
        solve(v);
        for (int j=min(size[u], m+1); j>=2; j--)
            for (int k=0; k<=min(size[v], j-1); k++)
                f[u][j]=max(f[u][j], f[u][j-k]+f[v][k]); 
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i=1, x; i<=n; i++){
        scanf("%d%d", &x, &dist[i]);
        G[x].push_back(i);
    }
    memset(f, 0, sizeof f);
    build(0);
    solve(0);
    printf("%d\n", f[0][m+1]);
    return 0;
}

CTSC1998 选课(背包类树形Dp)

原文:https://www.cnblogs.com/xiannvzuimei/p/9961214.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!