树形DP

2021-07-31 18:43:55

切题ing！！！！！

HDU  2196 Anniversary party

经典树形DP，以前写的太搓了，终于学会简单写法了....

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <map>

#include <queue>

#include <set>

#include <vector>

#define MOD 100000000

#define LL __int64

using namespace std;

int dp[][];

struct node

{

    int u,v,next;

}edge[];

int first[];

int flag[];

int p[];

int t;

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t ++;

}

int dfs(int x,int st,int fa)

{

    int sum = ,i,v;

    if(dp[x][st] != -)

    return dp[x][st];

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        dfs(v,,x);

        dfs(v,,x);

        if(st == )

        sum += max(dp[v][],dp[v][]);

        else

        sum += dp[v][];

    }

    if(st == )

    return dp[x][] = sum + p[x];

    else

    return dp[x][] = sum;

}

int main()

{

    int n,i,u,v;

    while(scanf("%d",&n)!=EOF)

    {

        CL();

        memset(dp,-,sizeof(dp));

        for(i = ;i <= n;i ++)

        {

            scanf("%d",&p[i]);

        }

        memset(flag,,sizeof(flag));

        for(;;)

        {

            scanf("%d%d",&u,&v);

            if(!u&&!v) break;

            add(v,u);

            flag[u] = ;

        }

        for(i = ;i <= n;i ++)

        {

            if(!flag[i])

            add(,i);

        }

        printf("%d\n",dfs(,,-));

    }

    return ;

}

HDU 2196 Computer

经典两次DFS，树形DP，也可以用最长路来做，我以前会的，忘了好多...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <map>

#include <queue>

#include <set>

#include <vector>

#define MOD 100000000

#define LL __int64

using namespace std;

int dp[][];

int ans[];

int flag[];

struct node

{

    int u,v,w,next;

}edge[];

int t;

int first[];

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

}

void add(int u,int v,int w)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].w = w;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs1(int x)

{

    int i,v,max1 = ,max2 = ;

    flag[x] = ;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(flag[v]) continue;

        dfs1(v);

        if(max1 < dp[v][] + edge[i].w)

        {

            max2 = max1;

            max1 = dp[v][] + edge[i].w;

        }

        else if(max1 == dp[v][] + edge[i].w)

        max2 = dp[v][] + edge[i].w;

        else if(max2 < dp[v][] + edge[i].w)

        max2 = dp[v][] + edge[i].w;

    }

    dp[x][] = max1;

    dp[x][] = max2;

}

void dfs2(int x,int fa)

{

    int i,v;

    flag[x] = ;

    ans[x] = max(dp[x][],fa);

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(flag[v]) continue;

        if(dp[x][] == dp[v][] + edge[i].w)

        dfs2(v,max(fa,dp[x][])+edge[i].w);

        else

        dfs2(v,max(fa,dp[x][])+edge[i].w);

    }

}

int main()

{

    int i,n,v,w;

    while(scanf("%d",&n)!=EOF)

    {

        CL();

        for(i = ;i <= n;i ++)

        {

            scanf("%d%d",&v,&w);

            add(v,i,w);

            add(i,v,w);

        }

        memset(flag,,sizeof(flag));

        dfs1();

        //for(i = 1;i <= n;i ++)

        //printf("%d %d\n",dp[i][0],dp[i][1]);

        memset(flag,,sizeof(flag));

        dfs2(,);

        for(i = ;i <= n;i ++)

        printf("%d\n",ans[i]);

    }

    return ;

}

HDU 1054 Strategic Game

以前做的时候，看错题了...这题是把所有的路，放一个士兵看守，那么如果根不放士兵，那么所有的子节点都要放。

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

using namespace std;

#define INF 100000000

struct node

{

    int u,v,next;

}edge[];

int dp[][];

int flag[];

int t;

int first[];

void CL()

{

    t = ;

    memset(flag,,sizeof(flag));

    memset(dp,,sizeof(dp));

    memset(first,-,sizeof(first));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs(int x)

{

    int i,v;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        dfs(v);

    }

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        dp[x][] += min(dp[v][],dp[v][]);

        dp[x][] += dp[v][];

    }

    dp[x][] ++;

}

int main()

{

    int i,j,n,m,u,v;

    while(scanf("%d",&n)!=EOF)

    {

        CL();

        for(i = ;i <= n;i ++)

        {

            scanf("%d:(%d)",&u,&m);

            for(j = ;j <= m;j ++)

            {

                scanf("%d",&v);

                flag[v] = ;

                add(u,v);

            }

        }

        for(i = ;i < n;i ++)

        {

            if(!flag[i])

            {

                dfs(i);

                printf("%d\n",min(dp[i][],dp[i][]));

                break;

            }

        }

    }

    return ;

}

POJ 3107 Godfather

水题....

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

using namespace std;

#define INF 100000000

struct node

{

    int u,v,next;

} edge[];

int first[];

int dp[];

int dis[];

int t;

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

    memset(dp,,sizeof(dp));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t ++;

}

int n;

void dfs(int x,int fa)

{

    int i,v,temp = ;

    for(i = first[x]; i != -; i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        dfs(v,x);

        temp += dp[v];

    }

    dp[x] = temp;

    dis[x] = n - temp;

    for(i = first[x]; i != -; i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        dis[x] = max(dis[x],dp[v]);

    }

}

int main()

{

    int i,u,v;

    while(scanf("%d",&n)!=EOF)

    {

        CL();

        for(i = ; i < n-; i ++)

        {

            scanf("%d%d",&u,&v);

            add(u,v);

            add(v,u);

        }

        dfs(,-);

        int ans = INF;

        for(i = ; i <= n; i ++)

        {

            ans = min(ans,dis[i]);

        }

        int flag = ;

        for(i = ; i <= n; i ++)

        {

            if(ans == dis[i])

            {

                if(flag)

                    printf(" ");

                flag = ;

                printf("%d",i);

            }

        }

        printf("\n");

    }

    return ;

}

POJ 1155 TELE

分组背包，1Y哦，注意背的顺序，调了小会。。

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

using namespace std;

#define INF 100000000

struct node

{

    int u,v,w,next;

} edge[];

int dp[][];

int p[];

int lf[];

int first[];

int t,n,m;

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

    memset(p,,sizeof(p));

    memset(lf,,sizeof(lf));

}

void add(int u,int v,int w)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].w = w;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs(int x)

{

    int i,j,k,v,w,sum = ;

    if(first[x] == -)

    {

        dp[x][] = p[x];

        lf[x] = ;

        return ;

    }

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        dfs(v);

        sum += lf[v];

    }

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        w = edge[i].w;

        for(j = sum;j >= ;j --)

        {

            for(k = ;k <= min(j,lf[v]);k ++)

            {

                if(dp[v][k] == -INF) continue;

                dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j-k] - w);

            }

        }

    }

    lf[x] = sum;

}

int main()

{

    int i,j,k,v,w;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        CL();

        for(i = ;i <= n;i ++)

        {

            for(j = ;j <= n;j ++)

            dp[i][j] = -INF;

        }

        for(i = ;i <= n-m;i ++)

        {

            scanf("%d",&k);

            for(j = ;j <= k;j ++)

            {

                scanf("%d%d",&v,&w);

                add(i,v,w);

            }

        }

        for(i = n-m+;i <= n;i ++)

        {

            scanf("%d",&p[i]);

        }

        dfs();

        for(i = m;i >= ;i --)

        {

            if(dp[][i] >= )

            break;

        }

        printf("%d\n",i);

    }

    return ;

}

HDU 1011 Starship Troopers

分组背包，这个题意坑啊。如果想往下走，必须把根节点的bug消灭。

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

using namespace std;

#define INF 100000000

struct node

{

    int u,v,next;

} edge[];

int p[];

int w[];

int first[];

int flag[];

int dp[][];

int t,n,m;

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

    memset(dp,,sizeof(dp));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs(int x)

{

    int i,j,k,v,pre;

    flag[x] = ;

    pre = (p[x]+)/;

    for(i = pre;i <= m;i ++)

    dp[x][i] = w[x];

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(flag[v]) continue;

        dfs(v);

        for(j = m;j >= pre;j --)

        {

            for(k = ;k + pre <= j;k ++)//保证j-k>=pre，保证能消灭bug

            {

                dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j-k]);

            }

        }

    }

}

int main()

{

    int i,u,v;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n < ) break;

        CL();

        memset(flag,,sizeof(flag));

        for(i = ;i <= n;i ++)

        {

            scanf("%d%d",&p[i],&w[i]);

        }

        for(i = ;i < n;i ++)

        {

            scanf("%d%d",&u,&v);

            add(u,v);

            add(v,u);

        }

        if(m == )

        {

            printf("0\n");

            continue;

        }

        dfs();

        printf("%d\n",dp[][m]);

    }

    return ;

}

HDU 1561 The more, The Better

挺简单的，注意 顺序和范围。

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

using namespace std;

#define INF 100000000

struct node

{

    int u,v,next;

}edge[];

int first[];

int dp[][];

int p[];

int t,m;

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

    memset(dp,,sizeof(dp));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs(int x)

{

    int i,j,k,v;

    for(i = ;i <= m;i ++)

    dp[x][i] = p[x];

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        dfs(v);

        for(j = m;j >= ;j --)

        {

            for(k = ;k < j;k ++)

            dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j-k]);

        }

    }

}

int main()

{

    int n,i;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n == &&m == ) break;

        CL();

        m ++;

        for(i = ;i <= n;i ++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            p[i] = v;

            add(u,i);

        }

        dfs();

        printf("%d\n",dp[][m]);

    }

    return ;

}

POJ 2486 Apple Tree

三种转移，少了一种....

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <vector>

using namespace std;

#define LL long long

struct node

{

    int u,v,next;

}edge[];

int p[];

int first[];

int flag[];

int dp[][][];

int t,n,m;

void CL()

{

    t = ;

    memset(flag,,sizeof(flag));

    memset(first,-,sizeof(first));

    memset(dp,,sizeof(dp));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs(int x)

{

    int i,v,j,k;

    flag[x] = ;

    dp[x][][] = dp[x][][] = p[x];

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(flag[v]) continue;

        dfs(v);

        for(j = m;j >= ;j --)

        {

            for(k = ;k <= j;k ++)

            {

                if(j--k >= )

                dp[x][j][] = max(dp[x][j][],dp[x][j--k][]+dp[v][k][]);

                if(j--k >= )

                {

                    dp[x][j][] = max(dp[x][j][],dp[x][j--k][] + dp[v][k][]);

                    dp[x][j][] = max(dp[x][j][],dp[x][j--k][]+dp[v][k][]);

                }

            }

        }

    }

}

int main()

{

    int u,v,i;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        CL();

        for(i = ;i <= n;i ++)

        scanf("%d",&p[i]);

        for(i = ;i < n;i ++)

        {

            scanf("%d%d",&u,&v);

            add(u,v);

            add(v,u);

        }

        dfs();

        int ans = ;

        for(i = ;i <= m;i ++)

        {

            ans = max(ans,dp[][i][]);

            ans = max(ans,dp[][i][]);

        }

        printf("%d\n",ans);

    }

    return ;

}

HDU 3586 Information Disturbing

乱搞。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <queue>

using namespace std;

#define INF 1000000000

struct node

{

    int u,v,w,next;

}edge[];

int first[];

int flag[];

int dp[][];

int t,maxz;

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

}

void add(int u,int v,int w)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].w = w;

    edge[t].next = first[u];

    first[u] = t ++;

}

void dfs(int x,int fa)

{

    int v,i,j,temp,sum,num = ;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        dfs(v,x);

        num ++;

    }

    if(num == ) return ;

    for(i = ;i <= maxz;i ++)

    {

        sum = ;

        for(j = first[x];j != -;j = edge[j].next)

        {

            v = edge[j].v;

            if(v == fa) continue;

            if(i >= edge[j].w)

            temp = min(edge[j].w,dp[v][i]);

            else

            temp = dp[v][i];

            if(temp == INF)

            {

                dp[x][i] = INF;

                break;

            }

            sum += temp;

        }

        if(j == -)

        dp[x][i] = sum;

    }

}

int main()

{

    int n,m,i,j;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n == &&m == ) break;

        CL();

        maxz = ;

        for(i = ;i < n;i ++)

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            maxz = max(maxz,w);

            add(u,v,w);

            add(v,u,w);

        }

        for(i = ;i <= n;i ++)

        {

            for(j = ;j <= maxz;j ++)

            dp[i][j] = INF;

        }

        dfs(,-);

        for(i = ;i <= maxz;i ++)

        {

            if(dp[][i] <= m) break;

        }

        if(i == maxz + )

        printf("-1\n");

        else

        printf("%d\n",i);

    }

    return ;

}

HDU 4276 The Ghost Blows Light

感觉和吃苹果那个有点像，想了一个4维DP，然后妥妥的TLE了，然后想了想发现1到n，是必须走的，分着处理出来，减去这条必须走的，继续分组背包，写的很麻烦dp[i][j]，表示以i为根花费j的回到i得到最大价值。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

using namespace std;

int dp[][];

int flag[];

int first[];

int pre[];

int p[];

int sum[];

int t,n,m;

struct node

{

    int u,v,w,next;

}edge[];

void CL()

{

    t = ;

    memset(first,-,sizeof(first));

    memset(flag,,sizeof(flag));

    memset(sum,,sizeof(sum));

    memset(dp,,sizeof(dp));

}

void add(int u,int v,int w)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].w = w;

    edge[t].next = first[u];

    first[u] = t ++;

}

void find(int x,int fa)

{

    int i,v;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        pre[v] = x;

        sum[v] = sum[x] + edge[i].w;

        find(v,x);

    }

}

void dfs(int x)

{

    int i,v,w,j,k;

    flag[x] = ;

    dp[x][] = p[x];

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        w = edge[i].w;

        if(flag[v]) continue;

        if(v == pre[x]) continue;

        dfs(v);

        for(j = m;j >= ;j --)

        {

            for(k = ;k <= j;k ++)

            {

                if(j-k-*w >= )

                dp[x][j] = max(dp[x][j],dp[x][j-k-*w] + dp[v][k]);

            }

        }

    }

}

int main()

{

    int u,v,w,i,k;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        CL();

        for(i = ;i < n;i ++)

        {

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w);

            add(v,u,w);

        }

        for(i = ;i <= n;i ++)

        scanf("%d",&p[i]);

        find(,-);

        if(sum[n] > m)

        {

            printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");

            continue;

        }

        int x = n;

        m -= sum[n];

        while()

        {

            dfs(x);

            for(i = m;i >= ;i --)

            {

                for(k = ;k <= i;k ++)

                {

                    dp[][i] = max(dp[][i],dp[][i-k]+dp[x][k]);

                }

            }

            if(x == ) break;

            x = pre[x];

        }

        int maxz = ;

        for(i = ;i <= m;i ++)

        maxz = max(maxz,dp[][i]);

        printf("%d\n",maxz);

    }

    return ;

}

/*

3 0

1 2 2

1 3 0

1 2 3

*/

URAL 1389. Roadworks

尚大婶 说这题很水。。。必须水过去，dp[i][0]表示i点子树的道路没有被封，dp[i][1]表示i点在子树已经有道路被封了。

dp[i][0] = sum(dp[v][1]);

dp[i][1] = sum(dp[v][1]) + max(dp[v][0]-dp[v][1]) + 1;

找路径扯淡一点，爆栈，加代码就水过了。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

using namespace std;

int dp[][];

int first[];

int flag[];

int t;

struct node

{

    int u,v,next;

}edge[];

int qu[];

int qv[];

int o[];

void CL()

{

    t = ;

    memset(o,,sizeof(o));

    memset(first,-,sizeof(first));

    memset(flag,,sizeof(flag));

    memset(dp,,sizeof(dp));

}

void add(int u,int v)

{

    edge[t].u = u;

    edge[t].v = v;

    edge[t].next = first[u];

    first[u] = t++;

}

void dfs(int x)

{

    int i,v,maxz = -,tf;

    flag[x] = ;

    tf = ;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(flag[v]) continue;

        tf = ;

        dfs(v);

        dp[x][] += dp[v][];

        maxz = max(maxz,dp[v][]-dp[v][]);

    }

    if(tf)

    {

        dp[x][] = dp[x][] = ;

        return ;

    }

    dp[x][] = dp[x][] + maxz + ;

}

void find(int x,int y,int fa)

{

    int i,v,maxz = -,tf = ,z;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        maxz = max(maxz,dp[v][]-dp[v][]);

        tf = ;

    }

    if(tf) return ;

    z = ;

    for(i = first[x];i != -;i = edge[i].next)

    {

        v = edge[i].v;

        if(v == fa) continue;

        if(y == )

        find(v,,x);

        else

        {

            if(maxz == dp[v][]-dp[v][]&&z)

            {

                find(v,,x);

                o[(i+)/] = ;

                z = ;

            }

            else

            find(v,,x);

        }

    }

}

int main()

{

    int n,m,i;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        CL();

        for(i = ;i <= m;i ++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            qu[i] = u;

            qv[i] = v;

            add(u,v);

            add(v,u);

        }

        dfs();

        printf("%d\n",dp[][]);

        find(,,-);

        for(i = ;i <= m;i ++)

        {

            if(o[i])

            printf("%d %d\n",qu[i],qv[i]);

        }

    }

    return ;

}
上一篇：106、Java中String类之使用contains()方法判断子字符串是否存在


下一篇：Uart串口与RS232串口的区别