题解

74 条题解

  • 2
    @ 2017-09-02 11:20:42

    一道水题....典型树归
    可参考“选课”,不同的是这题取了根节点就不能取左子树
    不过我并不知道时间复杂度是怎么保证的(粗看要o(nm^2))orz……

    #include<bits/stdc++.h>
    using namespace std;
    
    int lson[1030], rson[1030], c[1030], e[1030], f[1030][115];
    
    int dfs(int u, int x){
        if(u<0) return 0;                        //没人可以加入了
        if(f[u][x]!=-1) return f[u][x];
        int ret=0;
        for(int i=0;i<=x;i++)                    //这两行是根节点不选
                ret=max(ret, dfs(lson[u], i)+dfs(rson[u], x-i));
        if(x>=c[u]) ret=max(ret, e[u]+dfs(rson[u], x-c[u]));//根节点选
        return f[u][x]=ret;
    }
    
    int main()
    {
        memset(f, -1, sizeof(f));
        memset(lson, -1, sizeof(lson));
        memset(rson, -1, sizeof(rson));//这两个-1是判断有没有儿子
        int n, m; cin>>n>>m;
        for(int i=2;i<=n;i++){ int u; scanf("%d", &u); rson[i]=lson[u]; lson[u]=i; }
        for(int i=1;i<=n;i++) scanf("%d", &c[i]);
        for(int i=1;i<=n;i++) scanf("%d", &e[i]);
        cout<<dfs(1, m)<<endl;        //1保证是根
        return 0;
    }
    
    

    ps:貌似那个所有子节点的编号都比父节点的编号小的性质我没用到qwq

  • 1
    @ 2017-06-26 19:27:11

    这题实际上是一个01背包,如果用树形动规去写的话很可能超时。
    题目中有个特殊性质:所有子节点的编号都比父节点的编号小,通过这个性质我们可以倒序处理,用子节点的值求父节点的值;
    last[i]表示所有被处理过的i的子节点中最后一个被处理的节点的编号
    f[i][j]表示n到i中由i及其兄弟节点为根的树构成的森林用不超过j的费用的最大活跃值。

    #include<cstdio>
    #include<algorithm>
    #define ll long long
    #define R register
    using std::max;

    ll n,m,last[1025],p[1025][3],f[1025][110];

    int main(){
    scanf("%lld%lld",&n,&m);
    for (R int i=0;i<3;++i)
    for (R int j=i?1:2;j<=n;++j) scanf("%lld",&p[j][i]);
    for (R int i=n;i;--i){
    for (R int k=0;k<=m;++k){
    if (!last[p[i][0]]){
    f[i][k]=f[last[i]][k];
    if (p[i][1]<=k) f[i][k]=max(f[i][k],p[i][2]);
    }
    else {
    f[i][k]=f[last[p[i][0]]][k];
    if (p[i][1]<=k) f[i][k]=max(f[i][k],p[i][2]+f[last[p[i][0]]][k-p[i][1]]);
    for (R int t=0;t<=k;++t)
    f[i][k]=max(f[i][k],f[last[i]][t]+f[last[p[i][0]]][k-t]);
    }

    }
    last[p[i][0]]=i;
    }
    printf("%lld",f[1][m]);
    }

  • 1
    @ 2009-08-19 20:52:53

    这道题与经典的公司聚会不同,因为上司的定义由父结点改为了所有祖先。这样问题也由树形dp变为了01背包。

    由于题目中有一个非常重要的条件,“员工的编号会大于他的直接上司的编号”。这使得我们可以直接循环而不用建立树结构。

    用F来表示

    1)结点I的子树(不包括I结点)用J的花费可获得的最大值 在未循环到I时

    2)结点I的子树(可能包括I结点)用J的花费可获得的最大值 在循环到I以后

    1)在循环到I结点之前,已经把I结点的所有儿子处理过了,所以在处理I之前就可以先用I结点儿子的信息计算不取I结点所能获得的最大值。即在循环到I结点的儿子X时,把F[X,K](0

  • 0
    @ 2017-09-24 19:28:43
    #include <bits/stdc++.h>
    #include <climits>
    using namespace std;
    #define maxxn 1100
    #define maxxm 120
    int N, M, C[maxxn], E[maxxn];
    int F[maxxn][maxxm];
    struct Edges{
        int l, r;
    }T[maxxn];
    
    void Putin()
    {
        cin >> N >> M;
        memset(T, 0, sizeof(T));
        int root;
        for(int i = 2; i <= N; i++){
            cin >> root;
            T[i].r = T[root].l;
            T[root].l = i;
        }
        for(int i = 1; i <= N; i++)    cin >> C[i];
        for(int i = 1; i <= N; i++)    cin >> E[i];
        for(int i = 0; i <= 1025; i++)
            for(int k = 0; k <= 110; k++)
                F[i][k] = -(1024 * 1024);
    }
    
    inline void DP_dfs(int root)
    {
        if(root == 0)     return;
        DP_dfs(T[root].l), DP_dfs(T[root].r);
        for(int k = M; k >= C[root]; k--)
            F[root][k] = max(F[root][k], E[root]);//只选择root;
        if(T[root].l > 0 && T[root].r > 0)
            for(int i = 0; i <= M; i++)
                for(int k = 0; k <= i; k++)
                    F[root][i] = max(F[T[root].l][k] + F[T[root].r][i - k], F[root][i]);
                    //不选root,选择左子树和右子树;
        if(T[root].l > 0)
            for(int i = 0; i <= M; i++)
                F[root][i] = max(F[root][i], F[T[root].l][i]);//不选root,只选择左子树;
        if(T[root].r > 0)
            for(int i = 0; i <= M; i++){
                if(i - C[root] >= 0)
                    F[root][i] = max(F[root][i], F[T[root].r][i - C[root]] + E[root]);
                    //选择root和右子树;
                F[root][i] = max(F[T[root].r][i], F[root][i]);//只选择右子树;
            }
        return;
    }
    
    int main()
    {
        Putin();
        DP_dfs(1);
        cout << F[1][M] << endl;
        return 0;
    }
    
    
  • 0
    @ 2017-04-04 12:55:12

    #include<cstdio>
    #include<cstring>
    #include<cctype>
    #include<algorithm>
    #include<vector>

    using namespace std;

    int C[1030],E[1030],n,m;
    int f[1030][120];
    vector<int> tree[1030];

    void calc(int id){
    int i,j,k,branch_n;
    for(i = 0;i<(int)tree[id].size();i++)
    calc(tree[id][i]);
    for(i = 0;i<(int)tree[id].size();i++) {
    branch_n = tree[id][i];
    for(j = m;j>=0;j--) {//两个循环都要从后往前
    for(k = j;k>=0;k--){
    f[id][j] = max(f[id][j],f[branch_n][j-k]+f[id][k]);
    }
    }
    }
    for(i = m;i-C[id]>=0;i--) f[id][i] = max(f[id][i],E[id]);
    }

    int main(){
    //freopen("data.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int i,tmp;
    scanf("%d%d",&n,&m);
    for(i = 2;i<=n;i++) {
    scanf("%d",&tmp);
    tree[tmp].push_back(i);
    }
    for(i = 1;i<=n;i++) scanf("%d",&C[i]);
    for(i = 1;i<=n;i++) scanf("%d",&E[i]);
    memset(f,0,sizeof(f));
    calc(1);
    printf("%d\n",f[1][m]);
    return 0;
    }

  • 0
    @ 2017-01-29 15:44:21
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    struct node1
    {
        int h,c,e,sn,s[1025];
    }a[1025];
    
    int n,m,f[1025][110];
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            a[i].sn=0;
            memset(a[i].s,0,sizeof(a[i].s));
        }
        a[1].h=0;
        for (int i=2;i<=n;i++)
        {
            scanf("%d",&a[i].h);
            a[a[i].h].s[++a[a[i].h].sn]=i;
        }
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i].c);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i].e);
        memset(f,0,sizeof(f));
        for (int i=n;i>=1;i--)
        {
            for (int k=1;k<=a[i].sn;k++)
                for (int j=m;j>=0;j--)
                    for (int t=0;t<=j;t++)
                        f[i][j]=max(f[i][j],f[i][j-t]+f[a[i].s[k]][t]);
            for (int j=m;j>=a[i].c;j--)
                f[i][j]=max(f[i][j],a[i].e);
        }
        printf("%d\n",f[1][m]);
    }
    
    • @ 2017-01-29 15:45:02

      很H2O的背包

  • 0
    @ 2016-05-10 19:06:52
    //迭代深搜
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int MAXN = 1024 + 5;
    const int MAXM = 109 + 5;
    int n, m, ec = 0, fa, c[MAXN], e[MAXN], fst[MAXN], to[MAXN << 1], next[MAXN];
    
    inline void add(int f, int t) {
        to[++ec] = t;
        next[ec] = fst[f];
        fst[f] = ec;
    }
    
    int f[MAXN][MAXM], g[MAXN][MAXM], cur[MAXN], s[MAXN], top = 0;
    bool vis[MAXN];
    
    int main() {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n, &m);
        for (int i = 2; i <= n; i++) {
            scanf("%d", &fa);
            add(fa, i);
        }
        for (int i = 1; i <= n; i++)scanf("%d", &c[i]);
        for (int i = 1; i <= n; i++)scanf("%d", &e[i]);
        s[top++] = 1;
        vis[1] = true;
        memcpy(cur, fst, sizeof(fst));
        while (top) {
            int u = s[top - 1];
            vis[u] = true;
            if (cur[u]) {
                int v = to[cur[u]];
                if (!vis[v])s[top++] = v;
                cur[u] = next[cur[u]];
            } else {
                memset(f, 0, sizeof(f));
                int h = 0;
                for (int i = fst[u]; i; i = next[i]) {
                    h++;
                    for (int j = 0; j <= m; j++)
                        for (int k = 0; k <= j; k++)
                            f[h][j] = max(f[h][j], f[(h - 1)][k] + g[to[i]][j - k]);
                }
                memcpy(g[u], f[h], sizeof(f[h]));
                for (int j = 0; j <= m; j++)if (j >= c[u])g[u][j] = max(g[u][j], e[u]);
                top--;
            }
        }
        printf("%d\n", g[1][m]);
        return 0;
    }
    
  • 0
    @ 2016-05-10 16:02:50

    多叉转二叉以后确实简介不少。。。(好吧实际也没多少。。。)

    #include<cstdio>
    #include<iostream>
    #define MAXN 2005
    #define MAXM 205
    using namespace std;

    int n,m;

    int use[MAXN][2];
    int v[MAXN],w[MAXN];
    int f[MAXN][MAXM];

    void dfs(int i)
    {
    if(i==0)return ;
    dfs(use[i][0]),dfs(use[i][1]);
    for(int j=0;j<=m;j++)
    {
    for(int g=0;g<=j;g++)
    {
    f[i][j]=max(f[i][j],f[use[i][0]][g]+f[use[i][1]][j-g]);
    }
    }
    for(int j=m;j>=w[i];j--)
    f[i][j]=max(f[i][j],f[use[i][1]][j-w[i]]+v[i]);
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    int t1;
    for(int i=2;i<=n;i++)
    {
    scanf("%d",&t1);
    use[i][1]=use[t1][0];
    use[t1][0]=i;
    }
    for(int i=1;i<=n;i++)
    scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
    scanf("%d",&v[i]);
    dfs(1);

    printf("%d",f[1][m]);

    return 0;
    }

  • 0
    @ 2016-05-10 12:00:13

    总感觉哪里不对 。。。基本和楼下一样了。。。
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #define MAXN 2050
    #define MAXM 200
    #define LL long long
    using namespace std;

    int n,m;
    LL v[MAXN],w[MAXN];
    int fst[MAXN],next[MAXN],to[MAXN],poi=0;
    void add(int op,int ed)
    {next[++poi]=fst[op],fst[op]=poi,to[poi]=ed;return ;}

    LL max(LL a,LL b){return a>b? a:b;}

    LL f[MAXN][MAXM],tmp[MAXN][MAXM];
    int vis[MAXN];

    void dfs(int x)
    {
    vis[x]=1;
    for(int i=fst[x];i;i=next[i])if(!vis[to[i]])dfs(to[i]);
    memset(tmp,0,sizeof(tmp));
    int h=0;
    for(int i=fst[x];i;i=next[i])
    {
    h++;
    for(int j=0;j<=m;j++)
    {
    for(int g=0;g<=j;g++)
    {
    tmp[h][j]=max(tmp[h][j],tmp[h-1][g]+f[to[i]][j-g]);
    }
    }
    }
    for(int i=0;i<=m;i++)
    {
    f[x][i]=tmp[h][i];
    if(i>=w[x])f[x][i]=max(f[x][i],v[x]);
    }
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    int t1;
    for(int i=2;i<=n;i++)

    {
    scanf("%d",&t1);
    add(t1,i);
    }
    for(int i=1;i<=n;i++)
    scanf("%lld",&w[i]);
    for(int i=1;i<=n;i++)
    scanf("%lld",&v[i]);

    dfs(1);

    printf("%lld",f[1][m]);

    return 0;

    }

  • 0
    @ 2015-12-11 23:35:16

    数据给的109就是吓人的,还以为是10^9orz.....
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #define rep(i, x, y) for (int i = x; i <= y; ++i)

    using namespace std;

    const int maxn = 1 << 11, maxm = 1 << 7;

    struct Node {
    int nextNode;
    Node *next;
    } *N[maxn], pool[maxn << 1];
    int pool_cnt;
    int n, m;
    int c[maxn], e[maxn];

    void addedge(int x, int y) {
    Node *p = &pool[++pool_cnt];
    *p = (Node){y, N[x]};
    N[x] = p;
    }
    int vis[maxn];
    int f[maxn][maxm], g[maxn][maxm], cnt[maxn], son[maxn][maxn];

    void dfs(int i) {
    vis[i] = true;
    for (Node *p = N[i]; p; p = p->next) {
    if (!vis[p->nextNode]) {
    son[i][++cnt[i]] = p->nextNode;
    dfs(p->nextNode);
    }
    }
    memset(f, 0, sizeof (f));
    rep(j, 1, cnt[i]) rep(k, 0, m) rep(_k, 0, k)
    f[j][k] = max(f[j][k], f[j - 1][_k] + g[son[i][j]][k - _k]);
    rep(j, 0, m) {
    g[i][j] = f[cnt[i]][j];
    if (c[i] <= j) g[i][j] = max(e[i], g[i][j]);
    }
    }
    int main(int argc, const char *argv[]) {
    scanf("%d %d", &n, &m);
    rep(i, 2, n) {
    int y;
    scanf("%d", &y);
    addedge(i, y); addedge(y, i);
    }
    rep(i, 1, n) scanf("%d", &c[i]);
    rep(i, 1, n) scanf("%d", &e[i]);
    dfs(1);
    printf("%d\n", g[1][m]);
    return 0;
    }

  • 0
    @ 2015-08-15 08:36:23

    多叉树转二叉树后记忆化搜索,具体选择请看代码及注释。(由于转成二叉树后,根与左子树是父子关系,根与右子树是兄弟关系,所以选了根还可以选右子树,但一定不能选左子树)时间不太好看,最慢的一个点要900+ms,不过勉强能过。

    #include <stdio.h>
    #define LOWER_BOUND -100000000
    #define MAX_NUM 1500

    struct{
    int left, right, cost, value;
    } tree[MAX_NUM];
    int lastChild[MAX_NUM];
    int f[MAX_NUM][110]; //f[root][budget]

    int Max(int a, int b){
    return a>b ? a:b;
    }
    int search(int root, int budget){
    int i;
    if(f[root][budget]>LOWER_BOUND)
    return f[root][budget];
    if(budget<0)
    return LOWER_BOUND;
    //**if root is chosen, its left child cannot be chosen; its right child can be chosen**
    if(budget >= tree[root].cost){
    //---chooose root---
    f[root][budget] = tree[root].value; //choose root only
    if(tree[root].right >= 0)
    f[root][budget] = Max(f[root][budget], search(tree[root].right, budget-tree[root].cost) + tree[root].value); //right & root
    }
    //---not choose root---
    if(tree[root].right >= 0)
    f[root][budget] = Max(f[root][budget], search(tree[root].right, budget)); //right only
    if(tree[root].left >= 0)
    f[root][budget] = Max(f[root][budget], search(tree[root].left, budget)); //left only
    if(tree[root].left >= 0 && tree[root].right >= 0){
    for(i=0; i<=budget; i++)
    f[root][budget] = Max(f[root][budget], search(tree[root].left, i) + search(tree[root].right, budget-i)); //left & right
    }
    return f[root][budget];
    }
    int main(){
    int num, limit;
    int i, k;
    scanf("%d %d", &num, &limit);
    for(i=0; i<num; i++){
    for(k=0; k<=limit; k++)
    f[i][k] = LOWER_BOUND;
    tree[i].left = tree[i].right = -1;
    lastChild[i] = -1;
    }
    for(i=1; i<num; i++){
    scanf("%d", &k);
    --k;
    if(lastChild[k]<0)
    tree[k].left = i;
    else
    tree[lastChild[k]].right = i;
    lastChild[k] = i;
    }
    for(i=0; i<num; i++)
    scanf("%d", &tree[i].cost);
    for(i=0; i<num; i++)
    scanf("%d", &tree[i].value);
    printf("%d\n", search(0, limit));
    return 0;
    }

  • 0
    @ 2013-10-29 22:43:46

    一定要注意有c[i]=0
    ###Block Code
    var
    i,j,k,m,n,total:longint;
    p,ii:longint;
    fa,l,r:array[1..1024] of int64;
    f:array[1..1024,0..109] of int64;
    g:array[0..1024,0..109] of int64;
    c,e:array[1..1024] of int64;
    begin
    readln(n,total);
    fillchar(l,sizeof(l),0);
    fillchar(r,sizeof(r),0);

    for i:=2 to n do
    begin
    read(fa[i]);

    r[i]:=l[fa[i]];
    l[fa[i]]:=i;
    end;

    for i:=1 to n do
    read(c[i]);

    for i:=1 to n do
    read(e[i]);

    for ii:=n downto 1 do
    begin
    i:=l[ii];
    p:=0;
    fillchar(g,sizeof(g),0);
    while i<>0 do
    begin
    inc(p);
    for j:=0 to total do
    begin
    for k:=0 to total do
    begin
    if j-k<0 then continue;

    if g[p][j]<g[p-1][j-k]+f[i][k] then
    g[p][j]:=g[p-1][j-k]+f[i][k];
    end;
    end;

    i:=r[i];
    end;

    for i:=0 to total do
    f[ii][i]:=g[p][i];

    for i:=c[ii] to total do
    if f[ii][i]<e[ii] then
    f[ii][i]:=e[ii];
    end;

    writeln(f[1][total])
    end.

  • 0
    @ 2010-04-01 12:13:01

    利用惯性思维吓人……才110,不是10^9

  • 0
    @ 2009-11-03 21:29:26
    • -一个数组忘开Longint...........
  • 0
    @ 2009-11-02 16:58:16

    orz.... 01背包好啊,我一下子还真没看出来……

  • 0
    @ 2009-10-21 22:19:09

    for i:=n downto 1 do

    begin

    if c[i]

  • 0
    @ 2009-10-21 17:24:38

    树型DP 以前这道纠结半天- -\诶..我真沙茶

  • 0
    @ 2009-10-07 18:32:48

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    我的方法是o(n*m)的

    不是树形dp

  • 0
    @ 2009-09-25 23:45:28

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 41ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 56ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:218ms

    练练树归……

    =======================puppy的分割线=======================

    program v1418;

    var l,r,c,e:array[0..1030] of longint;

    f:array[0..1030,0..110] of longint;

    b:array[0..1030,0..110] of boolean;

    i,n,m,x:longint;

    function max(p,q:longint):longint;

    begin

    if p>q then exit(p) else exit(q);

    end;

    procedure dp(i,j:longint);

    var k:longint;

    begin

    if (i=0) then exit;

    if b then exit;

    if (j>=c[i])and(e[i]>0)

    then begin

    dp(r[i],j-c[i]);

    f:=f[r[i],j-c[i]]+e[i];

    end;

    for k:=0 to j do

    begin

    dp(l[i],k);

    dp(r[i],j-k);

    f:=max(f,f[l[i],k]+f[r[i],j-k]);

    end;

    b:=true;

    end;

    begin

    readln(n,m);

    for i:=2 to n do

    begin

    read(x);

    if l[x]=0 then l[x]:=i

    else begin

    r[i]:=l[x];

    l[x]:=i;

    end;

    end;

    for i:=1 to n do read(c[i]);

    for i:=1 to n do read(e[i]);

    fillchar(b,sizeof(b),false);

    dp(1,m);

    writeln(f[1,m]);

    end.

  • 0
    @ 2009-08-31 13:32:20

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 72ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 259ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:356ms

    好慢的treedp...

    我是sb...第一次没加记忆化就交了...TLE...

    于是想了两个剪枝

    if jsum[i] then j:=sum[i];

    min[i]是以i为根结点的子树c的最小值

    sum[i]是以i为根结点的子树c的和

    照样TLE...

    静态差错...发现少了最重要的

    if f0 then exit(f);

    果然什么剪枝都比不上记忆化...

信息

ID
1418
难度
5
分类
动态规划 | 树形DP 点击显示
标签
(无)
递交数
1007
已通过
343
通过率
34%
被复制
2
上传者