P2014 选课 树形dp

  

题目描述

在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有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很简单 但是多个就。。。

仔细观察可得 所有的树都连在0点 所以答案就是dp[0][m+1]

以后也可以用这种方法 连一个超级源点
P2014 选课 树形dp
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=6000+5;
const int M=50005;
int head[M],pos;
struct Edge
{
    int nex,to,v;
}edge[M];
void add(int a,int b)
{
    edge[++pos].nex=head[a];
    head[a]=pos;
    edge[pos].to=b;
}
int n,m;
int dp[N][N];

void dfs(int u)
{
    for(int i=head[u];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        dfs(v);
        for(int j=m+1;j>=1;--j)
        for(int k=j-1;k>=1;--k )
        dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k] );
    }
}

int main()
{
    RII(n,m);
    rep(i,1,n)
    {
        int a,b;RII(a,b);
        add(a,i);
        dp[i][1]=b;
    }
    dfs(0);
    cout<<dp[0][m+1];
    return 0;
}
View Code

 












上一篇:8.14.2. Designing JSON documents effectively


下一篇:洛谷P2014 选课(树形DP+分组背包)