洛谷2014 选课

Luogu

算法

显然课程构成树形关系,而且要从中选择一些,所以考虑树上分组背包。

设$f[i][j]$表示以$i$为根的子树,选$j$门课的最大学分。

那么有

$f[u][i]=max_{\text{v是u的儿子,}0\leq j\leq i}f[u][i-j]+f[v][j]$

边界是$f[i][0]=0$。

但是这个题可能是个森林,那么建一个0节点作为根节点。

程序中用了一些奇怪的方法

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline void chmax(int& a,int b) { if (b>a) a=b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; };
Edge e[910];
int head[310],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int n,m;
int a[310];

int f[310][310];

inline void Dfs(int u) {
    f[u][0]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; Dfs(v);
        for (re int j=m;j>=0;j--) {
            for (re int k=j;k>=0;k--)
                chmax(f[u][j],f[u][j-k]+f[v][k]);
        }
    }
    if (u) {
        for (re int i=m;i>0;i--) f[u][i]=f[u][i-1]+a[u];
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;i++) { addEdge(read(),i); a[i]=read(); }
    Dfs(0); printf("%d\n",f[0][m]);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 21 PM

4 条评论

  1. smy

    这哪里毒瘤了qwq

    1. M_sea
      @smy

      您比较强啊qwq

  2. ZCDHJ

    这个应该叫树上的分组背包吧

    1. M_sea
      @ZCDHJ

      已修改 qwq

发表评论 取消回复